I am always confused when I write a recursion program even a small one.
#include <iostream>
using namespace std;
int recursion(int x)
{
if(x == 0)
return 0;
return (x + recursion(x-1)); //recursive function call should always be in the return statement?
}
int main()
{
cout<<"SUM:"<<recursion(9);
}
Is there any another way by which recursive function call does not be in the return statement
There is no language rule saying that the recursive call has to appear as part of the return statement. It can appear anywhere in the method (perhaps even in several places).
For example:
int recursion(int x)
{
if (x == 0) return 0;
int rec = recursion(x-1);
return x + rec;
}
That said, making the recursive call right at the very end of the function has its benefits: this is called "tail recursion" and a good compiler might be able to optimize tail recursion away.
Finally, it's worth mentioning that in your particular example (summing the numbers from 0 to n) the recursion is completely unnecessary.
You can of course recurse in any fashion you like. For example, to compute Fibonacci numbers in the naive way, you have a recursion that necessarily branches extremely fast:
inf fib(int n)
{
//... base case
int a = fib(n - 1);
int b = fib(n - 2);
return a + b;
}
You can also write return fib(n-2) + fib(n-1);, but the point is that you cannot eliminate the recursive branching in this case.
On the other hand, what you really want to try and achieve is tail recursion, by which the final statement is nothing but the recursive call. For instance, your summation could be written as:
void sum(int n, int & result)
{
if (n = 0) return;
result += n;
sum(n - 1, result);
}
The key feature of this special case is that the recursion can take place entirely in-place. Generally, the stack grows as (B − 1)n, where n is the recursion depth and B is the number of parallel evaluations. This is exponential (read: bad), unless you have B = 1, in which case one can try and design the function as tail recursion.
When doing recursion, don't think of recursion. Think: "Ah, at this point it would be practical to call that recursion() function" or "Oh, I could re-use it here". They are normal function calls like all the other calls.
Recursion The Term unnecessarily confuses many upcoming programmers. If you understand functions and function calls, you already understand recursion, you just don't know yet.
You don't need to place the recursive function call into the return statement; you can just do:
int recursion(int x)
{
if(x == 0)
return 0;
int val = recursion(x-1);
return (x + rec);
}
