<

Introduction to Recursion

Published on
4,075 Points
1,075 Views
Last Modified:
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.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89
Iteration Steps:
The Fibonacci formula can be written as, F(n) = F(n - 1) + F(n - 2)
fibonacci(0) = 0
fibonacci(1) = 1
fibonacci(2) = fibonacci(1) + fibonacci(0) = 1 + 0 = 1
fibonacci(3) = fibonacci(2) + fibonacci(1) = 1 + 1 = 2
fibonacci(4) = fibonacci(3) + fibonacci(2) = 2 + 1 = 3
fibonacci(5) = fibonacci(4) + fibonacci(3) = 3 + 2 = 5
fibonacci(6) = fibonacci(5) + fibonacci(4) = 5 + 3 = 8

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
}

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

fibonacci(2) = fibonacci(2 - 1) + fibonacci(2 - 2) = fibonacci(1) + fibonacci(0) = 1 + 0 = 1


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

fibonacci(3) = fibonacci(3 - 1) + fibonacci(3 - 2) = fibonacci(2) + fibonacci(1) = 1 + 1 = 2  

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));
}

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.

recursionTree.jpg
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.

recursionTree-circled.jpg
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;
}

Open in new window

0
0 Comments

Featured Post

CompTIA Security+

Learn the essential functions of CompTIA Security+, which establishes the core knowledge required of any cybersecurity role and leads professionals into intermediate-level cybersecurity jobs.

I've attached the XLSM Excel spreadsheet I used in the video and also text files containing the macros used below. https://filedb.experts-exchange.com/incoming/2017/03_w12/1151775/Permutations.txt https://filedb.experts-exchange.com/incoming/201…
Watch this simple and effective video tutorial to extract attachments from Outlook 2007 and try this easy method by yourself. No need to go anywhere, just watch the video and export attachments from Outlook in few simple steps. To know more, click h…

Keep in touch with Experts Exchange

Tech news and trends delivered to your inbox every month