What is Recursion ?

Recursion is the way of making a function call itself. The below diagram shows that the function recurse is calling itself in it's body:

def func(): <--
              |
              | (recursive call)
              |
func() --------

Working of a Recursive step

1. Components of a recursive function

The condition that stops a recursive function to repeat endlessly is known as base condition and recursive step is the step executed when the base condition is satisified.

def func(a):    <------------
    if(a < 5):              |
        func(a+1)---------->| (recursive step)
    print(a)                |
func(0) -------------------> (here we are taking a as 0)

The above function print all numbers in range ( a to 5 ). The function stops executing as soon as the base condition is met. Below is the output .

If we remove the base condition it raises RecursionError . This happens because there is no restrictions on when the function should be called . Hence it is repeating the same function indefinitely. Check the output below :

  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded

Okay, by now you must have grabbed the concept of base case and recursive step. Yay 😎

2. Recursive Tree

If you think that the first recursive function is ended instantly as the last function is ended, then you are wrong.

What happens in recursion is that the first function calls the second function which in return calls the third function and so forth . A parent functions is ended only if all of it's children functions have ended.

main( ) <--- 
           | (returning to main() function)
func(0) <---
   ↓       |
func(1) <---
   ↓       |
func(2) <---
   ↓       |
func(3) <---
   ↓       |
func(4) ---> (returning to parent function)

The above diagram is known as Recursion Tree . It is the best way to visualize the recursion.

3. Head Recursion vs Tail Recursion

In head recursion you perform your recursive calls first, and then you take the return value of the recursive call and calculate the result. While, in tail recursion you perform your calculations first, and then you execute the recursive call, passing the results of your current step to the next recursive step.

Below is the code for head recursion :

def headrec(n):
    if(n == 0):
        return
    else:
        headrec(n-1)
    print(n)

Below is the code for tail recursion :

def tailrec(n):
    if(n == 1):
        return
    else:
        print(n)
    tailrec(n-1)

Examples

1. Calculate Sum of n Natural Numbers

def recurSum(n):
    if n <= 1:
        return n
    return n + recurSum(n - 1)

print(recurSum(100))

The output below shows the sum of n(100) natural numbers

Should I Use it or Not

Advantages	Disadvantages
___	___
Recursion adds clarity and sometimes reduces the time needed to write code.	Recursive solution is always logical and it is very difficult to trace.
Recursion helps to break down the problem into easy small steps.	It always needs an if condition.
Reduce unnecessary calling of functions.	Recursion uses more processor time.
Reduce overall size of code.	Can lead to stack overflow.

Thanks for reading .🙂

Everything about Recursion !

Table of contents