Introduction to Recursion

by

So first, what is a recursion? Well it’s anything that includes itself in its definition. When you yell your name loud at an edge of a valley and hear it echoing, that’s a physical world example of recursion.

While programming, we may sometimes write some function that call other ones. But if we include the same function in itself. That is calling the same function in itself. Then that is recursion. Below is a simple example for it.

def recursive():
  print("This is recursive function")
  recursive()

main()
  recursive()

In the above code, if you see the function named recursive. You will notice that it call itself inside it. So, this is called recursion: A function calling itself.

So, what do you think, how many time this code will run? Infinite. That why a recursion function needs to have a terminating or base condition. After base condition recursion calls will stop.

Example of Recursion

Let us look at a program to calculate factorial of a number. Factorial of a number is a product of itself by all numbers up to 1. For 0, its factorial is 1 i.e 0!=1 & factorial of negative number doesn’t exist. Below is the code, to produce a factorial of a number. 

def recur_factorial(n):
   if n == 1:
       return 1
   else:
       return n*recur_factorial(n-1)

num = 10

# check if the number is negative
if num < 0:
   print("Doesn't exist")
elif num == 0:
   print("The factorial of 0 is 1")
else:
   print("The factorial of", num, "is", recur_factorial(num))

Here, We are defining a function with argument as int n, first of all the base condition, it would be if n becomes equal to 1, the program would return 1. Now if n>1, then it will return n multiplied by (n-1) and now is time use our function again by calling it further in recursion. So this time we call it by passing the argument as int n-1. This chain goes on for n-2, n-3, … and so on up to 1. When n becomes equal to 1, the program starts returning the product up to n. And thus a factorial is generated.

Though recursion is an expensive approach (sometimes being inefficient), we can use the above program to calculate the factorial of 998. As the default maximum recursion depth is 1000 for python interpreter.

Now let us look at an interesting program to generate fibonacci series:

def fibonacci(n):
   if n <= 1:
       return n
   else:
       return(fibonacci(n-1) + fibonacci(n-2))

nterms = 10

# check if the number of terms is valid
if nterms <= 0:
   print("Please enter a positive integer")
else:
   print("Fibonacci sequence:")
   for i in range(nterms):
       print(fibonacci(i))

This a simple program to print all of the fibonacci sequence up to N. Fibonacci sequence is a sequence we get when we add two consecutive terms progressively. The first two terms of the Sequence are 0 and 1. Thus, 0+1=1, 1+1=2, 1+2=3, 2+3=5 and so on.

In this example we are defining a function, first we will ensure for the base condition i.e if n= 0 or n=1 then we will return the same. Every recursive function must have a base condition that stops the recursion or else the function calls itself infinitely. Here, our recursion will eventually end when the number reduces to 1. For number larger than 1, the function will call itself until it reduces to 1. Then after the base condition hits, function starts returning sum of two consecutive numbers.

Advantages of Recursion

Many algorithms are easy to write in recursion than iteration.

Complex problems can be split into simpler sub-problems through recursion and can be solved easily.

It is used in many algorithms/techniques like Dynamic Programming, Backtracking, etc.

Drawbacks of Recursion

Recursion uses more memory than Iteration.

It is expensive to perform thus being inefficient.

If recursion falls into infinite loops i.e infinite recursions, that results in stack overflows. In python, interpreter limits max depth to 1000.

Leave a Comment