Introduction to Recursion

Iteration:
Iteration is repetition of a process. A student who goes to school repeats the process of going to school everyday until graduation. We go to grocery store at least once or twice a month to buy products. We repeat this process every month. In mathematics, a Fibonacci sequence follows the properties of task repetation as well. Let’s consider the Fibonacci sequence where the first two numbers are 0 and 1, all other numbers are the sum of the previous two numbers.
Iteration Steps:
The Fibonacci formula can be written as, F(n) = F(n - 1) + F(n - 2)

The algorithm given below returns nth Fibonacci number.

public int fibonacci(int n) {
                      	int nth = 0;
                      	int nMinus2 = 0; // (n - 2)th fibonacci
                      	int nMinus1 = 1; // (n - 1)th fibonacci
                      	if(n == 0) return 0;
                      	if(n == 1) return 1;
                      	for(int i = 2; i <= n; ++i) {
                      		nth = nMinus1 + nMinus2; // nth fibonacci
                      		nMinus2 = nMinus1;
                      		nMinus1 = nth;
                      	}
                      	return nth; // nth fibonacci
                      }
                      

Select all Open in new window

Recursion:

Each time we get a new Fibonacci number (nth number) that nth number is actually (n - 1)th number when we find (n + 1)th Fibonacci as our next nth Fibonacci. As we see the iteration steps mentioned above: if n = 2 then



Now, we want to generate fibonacci(3), that is n = 3.


That means, each time n increases the value of current (n - 1)th and (n - 2)th fibonacci also increases. But it is tiring to keep track of (n - 1)th and (n - 2)th fibonacci for each n. How about writing a method that calls itself to repeat the task of iteration by itself?

A method that calls itself is named as recursive method. A recursive method must have a base case where the program stops calling itself. Our base case for Fibonacci series is fibonacci(0) = 0 and fibonacci(1) = 1. Otherwise, the Fibonacci method calls itself twice - fibonacci(n - 1) and fibonacci (n - 2). Then it adds them to get fibonacci(n). A recursive method for finding nth Fibonacci can be written as -  

public int fibonacciRecursion(int n) {
                      	if(n == 0) return 0;
                      	else if(n == 1) return 1;
                      	return (fibonacciRecursion(n - 1) + fibonacciRecursion(n - 2));
                      }
                      

Select all Open in new window

If we look carefully, recursion follows the property of stack. It solves smaller subproblems to get the solution of a problem. For n > 1, it execute the last line. So, if n = 6, The function calls and adds fibonacci(6 - 1) and fibonacci(6 - 2). fibonacci(6 - 1) or fibonacci(5) calls and adds fibonacci(5 - 1) and fibonacci(5 - 2). This recursion continues until 6 reaches down to its base case value which is fibonacci(0) = 0 or fibonacci(1) = 1. Once it hits the base case it adds two base values and goes up until it get the value of fibonacci(6). Below is a tree representation of recursion.


As we can see, how powerful a recursion can be. Only a single line of code is making the tree above (last line of the code above including base cases). Recursion maintains a stack and it goes to deeper until it reaches the base case.  

Dynamic Programming(DP):

Recursion is easy to understand and code but might be expensive in terms of time and memory. Take a look at the recursion tree below. The left subtree starting with fib(4) and the right subtree starting with fib(4) are exactly same. They generate the same result which is 3 but are doing the same task twice. If n is a big number(example: 500000) then recursion can make a program very slow as it would call same sub task multiple times.


To avoid this problem dynamic programming can be used. In dynamic programming we can use previously solved subtask to solve future task of same type. This is a way to reduce task for solving original problem. Let’s have an array fib[] where we store previously solved subtask solutions. We already know that fib[]0] = 0 and fib[]1] = 1. Let’s store these two values. Now, what is the value of fib[]2]? As fib[]0] = 0 and fib[]1] = 1 have been stored already we just have to say fib[]2] = fib[]1] + fib[]0] and that is all. We can generate fib[]3], fib[]4], fib[]5], ......, fib[n] in the same way. Previously solved subtasks are being called to get next subtask until the original task has not be solved, thus reduces redundant calculation.

public int[] fib(int n) {
                      	int[] fib = new int[n];
                      	f[0] = 0;
                      	f[1] = 1;
                      	for(int i = 2; i < n; ++i) {
                      		f[i] = f[i - 1] + f[i - 2];
                      	}
                       	return fib;
                      }
                      

Select all Open in new window