What is Recursion?

Recursion means “the repeated application of a recursive procedure or definition”. The adjective “recursive” originates from the Latin verb “recurrere”, which means “to run back”. In Recursion, the solution to the bigger problem is expressed in terms of smaller problems.

You can find many examples of recursion in mathematics for e.g.

1. The Factorial:

 n! = n * (n-1)!, if n > 1 and f(1) = 1

2. The Fibonacci sequence:

 fib(n) = fib(n-2) + fib(n-1);  fib(0) = fib(1) = 1 and n >= 0

“If I have to rate different mathematical concept according to its simplicity & practical applicability, then I will give ‘9 out of 10 rating’ to ‘Recursion / recurrence relation’. 90 % of my mathematical work involve this single principle.”
― Mathematician Vitthal Jadhav

In computer science, this is the process of solving a problem where a function calls itself directly or indirectly. The function that is repeatedly being called by itself is known as a recursive function.

How to solve a problem using recursion?

All recursive algorithms must have the following three stages:

1. Base Case – The base case is the solution to the “simplest” possible problem
2. Work toward Base Case to make the problem simpler.
3. Recursive Call (i.e., running back” or returning to itself)

The idea is to represent a problem in terms of one or more smaller problems and add one or more base conditions that stop the recursion. For example, we compute factorial n if we know factorial of (n-1). The base case for factorial would be n = 0. We return 1 when n = 0.

Example 1: Calculating the Factorial

n! = n * (n-1)!, if n > 1 and f(1) = 1

n! means the product of all the whole numbers from 1 to n; that is, n! = 1×2×3×…×n. For example, “four factorial” is written as “4!” and means 1×2×3×4 = 24.

Solution:

In the above example, the base case for n <= 1 is defined and larger value of a number can be solved by converting to smaller one till the base case is reached.

Example 2: Determine the nth Term of Fibonacci Series

The Fibonacci sequence is named after the mathematician Leonardo of Pisa, who is also famous as Fibonacci.

The Fibonacci series is defined by:

fib(n) = fib(n-2) + fib(n-1);  fib(0) = fib(1) = 1 and n >= 0

The Fibonacci numbers are the numbers in the following integer sequence.

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …

n	0	1	2	3	4	5	6	7	8
f(n)	1	1	2	3	5	8	13	21	34

Solution:

Can you identify the problem with the recursive solution?

 Recursion provides a clean and simple way to write code and it looks more like the mathematical definition, but our recursive solution doesn’t remember previously calculated values. To understand it better, let’s have a look at the calculation tree, i.e. the order in which the functions are called.

Here we can see that the subtree f(4) appears 2 times, the subtree for the calculation of f(3) appears three times and f(2) appears 5 times. If you imagine extending this tree for f(7), you will understand that f(5) will be called two times, f(4) three times, f(3) 5 times, f(2) 8 times and so on.

This means, our recursion doesn’t remember previously calculated values. All functions will remain in the memory stack until the base case is reached. As a result, the recursive program has greater space requirements. It also has greater time requirements because of repeated function calls and returns overhead.

An iterative approach to solve the problem:

This problem can also be solved using an iterative approach. In fact, every recursive program can be written iteratively and every iterative problem can be solved recursively.

This iterative approach to solve the Fibonacci use a much smaller amount of space. In this approach, each step through the loop uses only the previous two values of F(n). This requires some swapping around of values so that everything stays in the appropriate places.

Interesting Facts:

What do sunflowers, Shells, fir tree cones & Romanesque Broccoli have in common?

Right, the Fibonacci numbers.