Grokking Algorithms - Recursion

GROKKING ALGORITHMS - RECURSION

2022 April 21

Recursion does not have performance benefits. In fact, loops in specific situations can be better for performance.
“Loops may achieve a performance gain for a program. Recursion may achieve a performance gain for a programmer” (since it can result in algorithms with less steps or simpler to read).
A recursive function must be told when to stop recursing.
Every recursive function has 2 parts: the base case, and the recursive case.
The recursive case is when the function calls itself.
The base case is when the function does not call itself again - so it stops the loop.
A countdown can be a recursive function (eliminating for loops). Example:

def countdown(i):
    print(i)
    if i <= 0:
        return
    else:
        countdown(i-1)

A stack is a data structure that acts as a “pile”. When you insert a new item, you insert at the top of the stack (push). When you remove an item, you remove it from the top of the stack (pop).
A call stack is a pile of function calls, where one calls another.
Consider this function:

def greet(person):
    print(f'Hello {person}!')
    say_how_are_you(person)
    print('Getting ready to say bye...')
    bye()

In the example above, the call stack is like that:

You start the pile calling the greet function. It has a variable called person. The computer creates a stack to allocate this call in memory with the variable.
Then, you call print.
After, you call say_how_are_you, with the variable person. The computer allocates memory for this function call and the variable, on top of the greet function from step 1.
The computer does what it has to do on the say_how_are_you function. After it finishes, it gets popped (removed from the top of the call stack).
After removing say_how_are_you function from the top of the call stack, it is back to the greet function which is now at the top of the stack. It then calls the other print statement.
After, you call bye, with no variables. The computer allocates memory for this function call, on top of the greet function.
The computer does what it has to do on the bye function. After it finishes, it gets popped (removed from the top of the call stack).
After removing bye function from the top of the call stack, it is back to the greet function which is now at the top of the stack. The function has nothing left to do. So it is also removed from the call stack and the stack is now empty.

When you call a function from another, the calling function is paused in a partially completed state. The values of the calling function’s variables are stored in memory.
The stack used to save the variables for multiple functions is what is named as “call stack”.