Recursion is the concept of breaking a problem down continuously into smaller problems of the same type until the smaller chunks are trivial to solve, then using those answers to recompute the answer. However, not all problems can be solved using recursion. In general, there are 3 rules that all recursive solvable problems must obey.
Firstly, the problem must have the ability to be broken down into smaller parts. For example, in this case of a recursive solution to fibonacci, the solution to the nth fibonacci number is equal to the n-1th fibonacci number plus the n-2th fibonacci number, simplifying the problems.
Secondly, the problem solution must be able to be reformed from the solutions of the smaller problem (s). In the case of the factorial solution, when given the factorial of n-1, you can compute the factorial of n by multiplying n by the factorial of n-1.
Lastly, the problem must have a base case, where the problem can not be split any further and the answer is trivial. In the case of the fibonacci algorithm, this is when n is 0 or 1, where the answer is 1 for both.
To represent the recursion paradigm in code, we generally have two different types: Tail and Mutual recursion.
Tail Recursion:
Tail recursion means that the method calls itself at the end of every run. This generally means that the return statement contains the self call.
For example, a function that will calculate the sum of all numbers from 1 to n:
public int sum (int n){
if (n == 1){
return 1;
}
return n + sum(n-1);
}
Mutual Recursion:
Mutual recursion means that the method calls a separate method instead of itself. That method will then call this method again.
For example:
public int a (int param){
if (param < 0){
return 1;
}
return b(param-1) - param;
}
public int b(int param){
int (param < 0){
return param+1;
}
return a(param-1) - param;
}
}
Stack Trace for Tail and Mutual Examples
Let’s trace our example from Tail Recursion.
sum(5)
5 + sum(4)
5 + 4 + sum(3)
5 + 4 + 3 + sum(2)
5 + 4 + 3 + 2 + sum(1)
5 + 4 + 3 + 2 + 1
15
Let’s trace our example from Mutual Recursion.
b(5)
a(4) - 5
b(3) - 4 - 5
a(2) - 3 - 4 - 5
b(1) - 2 - 3 - 4 - 5
b(0) - 1 - 2 - 3 - 4 - 5
1 - 1 - 2 - 3 - 4 - 5
-14
In general, recursion is used because it is more easy to understand and program than iterative solutions. However, recursion is generally slower than iterative solutions because it requires of memory allocation time when the method call is stored in the stack.