Bhav Kushwaha

Posted on

# 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:

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.