DEV Community

Cover image for Chapter 3 : Recursion (Grokking Algorithms)
Bhav Kushwaha
Bhav Kushwaha

Posted on

Chapter 3 : Recursion (Grokking Algorithms)

Cover Image

Topics covered in Chapter 3 : Recursion

  1. What is Recursion?
  2. Base Case & Recursive Case
  3. The Stack
  4. Call Stack
  5. The Call Stack with Recursion

What is Recursion?

It is Explained using an Example of Grandma's Boxes & Key.

  • You want to open your Grandma's suitcase but the key to it is in this Box.

  • But this box contains more boxes inside those boxes. And the key is in a box somewhere.

  • Here we can use 2 Algorithms to find the key:

  1. Using Loops

  2. Using Recursion

An Image have two different approaches for solving the same box-key problem

Important Points to note:

  • There is no 100% guaranteed performance benefit of using recursion, infact sometimes loops perform better.

Base Case & Recursive Case

Every Recursive Function has two parts:-

Base Case

  • Here, the function doesn't call itself and thus this case prevents a chance of infinite loop.

Recursive Case

  • Here, the function calls itself again.

Base Case vs Recursive Case in a Function

The Stack

The best example to explain a stack is a Todo-List.
It enables two features : 1. Push() & 2. Pop()

Push & Pop in a stack

The Call Stack

Our computer uses a stack internally called the Call Stack.


def greet(name):
    print "hello, " + name + "!"
    print "getting ready to say bye..."
Enter fullscreen mode Exit fullscreen mode

This function calls 2 other functions:

def greet2(name):
    print "how are you, " + name + "?"
Enter fullscreen mode Exit fullscreen mode
def bye():
    print "ok bye!"
Enter fullscreen mode Exit fullscreen mode

Visually the above code is implemented:

  1. Greet Function() called

  2. Greet2 Function() called

  3. Greet2 is executed & then poped

  4. Bye Function() is called

  5. Bye is executed & then poped


  • Firstly Greet Function is called
  • Secondly Greet2 is called
  • Greet2 is executed and poped
  • Bye Function is called
  • Bye is executed and poped
  • In the end, Greet is returned too as there's nothing else to be done.

The Call Stack with Recursion

Explained by an Example - Factorial of a Number

The Code for Factorial :-

def fact(x):
 if x==1:
  return 1
  return x * fact(x-1)
Enter fullscreen mode Exit fullscreen mode

Factorial - Recursive Function implemented using a call stack


  • Using Stack is convenient but there's a cost; saving all that info can take up a lot of memory. Your Stack becomes too tall!

  • It can be solved using 1. Loops instead or 2. Tail Recursion

  • Suppose we write a recursive function that runs forever, then the program will run out of space & it will exit with a Stack-Overflow Error.

Top comments (0)