WikiGalaxy
Tail Recursion
Understanding Tail Recursion:
Tail recursion occurs when a recursive function makes a recursive call as its last operation. There is no need to retain the previous state of the function, making it more memory efficient.
Time Complexity:
The time complexity of tail recursion is similar to that of non-tail recursion, generally O(n) for linear recursion. However, optimization like tail call optimization (TCO) can reduce the space complexity to O(1).
Space Complexity:
With tail call optimization, space complexity can be reduced to O(1) as it reuses the current stack frame for the next recursive call.
Step 1: Diagram of a function call stack in tail recursion.
Step 2: Each call reuses the current stack frame.
Step 3: Final result is returned after the last call.
Step 4: No additional stack frames are needed.
public class TailRecursionExample {
public static void main(String[] args) {
System.out.println(factorial(5, 1));
}
public static int factorial(int n, int a) {
if (n == 0) return a;
return factorial(n - 1, n * a);
}
}
Explanation:
In the example above, the factorial function is tail recursive because the recursive call to factorial is the last thing executed by the function. The accumulator 'a' is used to carry the result.
Console Output:
120
Types of Recursion
1. Direct Recursion:
A function calls itself directly. Example: factorial, Fibonacci series.
2. Indirect Recursion:
A function calls another function, which in turn calls the first function. This can involve more than two functions.
3. Tail Recursion:
The recursive call is the last statement in the function. Optimized for space.
4. Non-Tail Recursion:
The recursive call is not the last statement in the function. Requires additional stack space.
5. Linear Recursion:
Each function makes at most one recursive call. Example: factorial.
6. Tree Recursion:
Each function makes multiple recursive calls. Example: Fibonacci series.
Example of Direct Recursion
Concept:
Direct recursion occurs when a function calls itself directly. It is the simplest form of recursion.
public class DirectRecursion {
public static void main(String[] args) {
System.out.println(sum(5));
}
public static int sum(int n) {
if (n <= 0) return 0;
return n + sum(n - 1);
}
}
Explanation:
This example calculates the sum of numbers from 1 to 5 using direct recursion. The function calls itself with a decremented value until it reaches the base case.
Console Output:
15
Example of Indirect Recursion
Concept:
Indirect recursion involves two or more functions calling each other in a circular manner.
public class IndirectRecursion {
public static void main(String[] args) {
functionA(20);
}
public static void functionA(int n) {
if (n > 0) {
System.out.println("A: " + n);
functionB(n - 1);
}
}
public static void functionB(int n) {
if (n > 0) {
System.out.println("B: " + n);
functionA(n / 2);
}
}
}
Explanation:
In this example, functionA calls functionB, which in turn calls functionA. The recursion continues until the base condition is met.
Console Output:
A: 20
B: 19
A: 9
B: 8
A: 4
B: 3
A: 1
Example of Non-Tail Recursion
Concept:
Non-tail recursion means the recursive call is not the last operation in the function, requiring additional operations after the call returns.
public class NonTailRecursion {
public static void main(String[] args) {
System.out.println(fibonacci(5));
}
public static int fibonacci(int n) {
if (n <= 1) return n;
return fibonacci(n - 1) + fibonacci(n - 2);
}
}
Explanation:
This example demonstrates a non-tail recursive function to calculate Fibonacci numbers. The function requires additional operations after the recursive calls return.
Console Output:
5
Example of Linear Recursion
Concept:
Linear recursion involves a function making a single recursive call per execution, creating a linear sequence of calls.
public class LinearRecursion {
public static void main(String[] args) {
printNumbers(5);
}
public static void printNumbers(int n) {
if (n <= 0) return;
System.out.println(n);
printNumbers(n - 1);
}
}
Explanation:
This example prints numbers from 5 to 1 using linear recursion, as each function call results in exactly one further call.
Console Output:
5
4
3
2
1
Example of Tree Recursion
Concept:
Tree recursion occurs when a function makes multiple recursive calls, leading to a tree-like structure of calls.
public class TreeRecursion {
public static void main(String[] args) {
System.out.println(fibonacci(5));
}
public static int fibonacci(int n) {
if (n <= 1) return n;
return fibonacci(n - 1) + fibonacci(n - 2);
}
}
Explanation:
This example calculates Fibonacci numbers using tree recursion, where each call to the function results in two further calls.
Console Output:
5
Example of Mutual Recursion
Concept:
Mutual recursion involves two or more functions calling each other in a cyclical manner, often used in parsing and grammar checks.
public class MutualRecursion {
public static void main(String[] args) {
System.out.println(isEven(4));
}
public static boolean isEven(int n) {
if (n == 0) return true;
return isOdd(n - 1);
}
public static boolean isOdd(int n) {
if (n == 0) return false;
return isEven(n - 1);
}
}
Explanation:
This example checks if a number is even or odd using mutual recursion, where isEven calls isOdd and vice versa.
Console Output:
true
Example of Nested Recursion
Concept:
Nested recursion occurs when a recursive function calls itself with the result of another recursive call.
public class NestedRecursion {
public static void main(String[] args) {
System.out.println(nestedRecursion(95));
}
public static int nestedRecursion(int n) {
if (n > 100) return n - 10;
return nestedRecursion(nestedRecursion(n + 11));
}
}
Explanation:
This example demonstrates nested recursion, where the function calls itself with the result of another call to itself, creating complex recursion patterns.
Console Output:
91
