Chapter 3 : Recursion (Grokking Algorithms)

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

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.

The Stack

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

The Call Stack

Our computer uses a stack internally called the Call Stack.

Example:

def greet(name):
    print "hello, " + name + "!"
    greet2(name)
    print "getting ready to say bye..."
    bye()

This function calls 2 other functions:

def greet2(name):
    print "how are you, " + name + "?"

def bye():
    print "ok bye!"

Visually the above code is implemented:

1. 

2. 

3. 

4. 

5. 

Explaination:

• 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
 else:
  return x * fact(x-1)

NOTE:

• 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.