Types of Recursion
1. Tail Recursion : Function call itself is the last statement. Operations perform at calling time of the recursion.
// Time complexity O(n) & Space complexity O(n)
void tail_recursion(int n) {
if(n > 0) {
System.out.print(n + " ");
tail_recursion(n - 1);
}
}
// Time complexity O(n) & Space complexity O(1)
void tail_recursion_iterative(int n) {
System.out.println();
while(n > 0) {
System.out.print(n + " ");
n--;
}
}
2. Head Recursion : Function call itself is the first statement. Operations perform at returning time of the recursion.
//Time complexity O(n) & Space complexity O(n)
void head_recursion(int n) {
if(n > 0) {
head_recursion(n - 1);
System.out.print(n + " ");
}
}
//Time complexity O(n) & Space complexity O(1)
void head_recursion_iterative(int n) {
System.out.println();
for(int i = 1; i <= n; i++) {
System.out.print(i + " ");
}
}
3. Linear Recursion : Operations perform at beginning & returning time of the recursion. Function call itself once.
void linear_recursion(int n) {
if(n > 0) {
System.out.print(n + " ");
linear_recursion(n - 1);
System.out.print(n + " ");
}
}
4. Tree Recursion : A recursive function calling itself more than one time.
//Time complexity O(2^n) and Space Complexity O(n)
void tree_recursion(int n) {
if(n > 0) {
System.out.print(n + " ");
tree_recursion(n - 1);
tree_recursion(n - 1);
}
}
5. Indirect Recursion: More than once functions calling each other recursively.
//Time complexity O(n)
void funA(int n) {
if(n > 0) {
System.out.print(n + " ");
funB(n - 1);
}
}
void funB(int n) {
if(n > 1) {
System.out.print(n + " ");
funA(n / 2) ;
}
}
6. Nested Recursion : return output of function is passed in recursion function.
int nested_recursion(int n) {
if(n > 100) {
return n - 10;
}
return nested_recursion(nested_recursion(n + 11));
}
Comments
Post a Comment