- Recursion
#include<iostream>
using namespace std;
void fun2(int n)
{
if (n>0)
{
fun2(n-1);
cout << n << endl;
}
}
int main()
{
int x=3;
fun2(x);
return 0;
}
- Output :
1 2 3
A good example of Recursion :
- Recursion has two phases : going and returning (ascending and descendig)
Difference b/w a loop and a recursion : Loop -> only ascending phase // Recursion -> Ascending and Descending phase.
Static and Global Variables in Recursion:
Static Variables:
If static variables are inside recursive function don’t show them in each tracing tree write them in global or outside variable and maintain a single copy of it.
Global Variable:
Here static and global variable will give the same result.
Types of Recursion:
- Tail Recursion
- Head Recursion
- Tree Recursion
- Indirect Recursion
- Nested Recursion
Tail Recursion:
If a recursive function is calling itself and that calling statement is the last statement in the function then it is called a recursive function.
- This is not a tail recursion as in tail recursion there doesn't have to be anything performed at the return time.
Converting Tail Recursion into a Loop :
- Here both are printing 3 values therefore time complexity for both of them is
3i.e Time -> O(n). - We know that Tail Recursive function here utilizes Stack therefore for
fun(3)it'll create 4 activation records in the stack. Where as in a Loop only 1 activation record will be created.
Therefore,
A loop is better than Tail Recursion.
Head Recursion:
- Recursive Function Call is made at the beginning of the function.
- At the time of calling the function doesn't have to perform anything and it has to do everything at the time of returning.
Converting Head Recursion to a Loop:
Tree Recursion:
If a recursive function is calling itself more than one time then it is called a Tree Recursion.
Indirect Recursion :
Nested Recursion:
Recursion inside recursion:
Interactive Graph
Table Of Contents