<

Introduction to Recursion

Published on
4,000 Points
1,000 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
Comment
0 Comments

Featured Post

Cloud Class® Course: Python 3 Fundamentals

This course will teach participants about installing and configuring Python, syntax, importing, statements, types, strings, booleans, files, lists, tuples, comprehensions, functions, and classes.

Join & Write a Comment

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…
Discover the basics of using Outlook 2016 from office 365.

Keep in touch with Experts Exchange

Tech news and trends delivered to your inbox every month