Recursion

Recursion is one of the most important concepts in computer science. Simply speaking, recursion is the process of a function calling itself. Using a real-life analogy, imagine a scenario where you invite your friends to lunch:

You first call Ben and ask him if he wants to go for lunch, and Ben says yes but he also wants to meet Sheldon, so he puts you on hold and calls Sheldon.

Sheldon answers Ben's call and says great but he also wants to meet Daniel, so he puts Ben on hold and calls Daniel.

Daniel answers Sheldon's call and says great but he also wants to meet Abdul, so he puts Sheldon on hold and calls Abdul.

Abdul answers Daniel's call and says great but he also wants to meet Dennis, so he puts Daniel on hold and calls Dennis.

Dennis answers Abdul's call and says great but he also wants to meet Carly, so he puts Abdul on hold and calls Carly.

Carly answers Dennis' call and says "ok let's go!" and hangs up.

Dennis returns to Abdul's call and says "ok let's go!" and hangs up.

Abdul returns to Daniel's call and says "ok let's go!" and hangs up.

Daniel returns to Sheldon's call and says "ok let's go!" and hangs up.

Sheldon returns to Ben's call and says "ok let's go!" and hangs up.

Ben returns to your call and says "ok let's go!" and hangs up.

You are happy and can now go to lunch!

Notice that the action of putting the previous person on hold and calling someone else is exactly the same except the person involved (the function argument) is different. Imagine this is a function call, it would be written as something like this:

1def call_for_lunch(person):
2    if person == 'Carly': # BASE CASE
3        return True
4    return call_for_lunch(next_person) # RECURSIVE CALL

This example highlights the key components in writing a correct recursive function:

1. Base case/exit, e.g. Carly doesn't call anyone else, she just says yes and hangs up.
2. Recursive call, i.e. calling the function itself with different argument, e.g. Ben calling Sheldon.

---

Here's a classic textbook example: finding the factorial of a number (5! = 5*4*3*2*1)

1def factorial(n):
2    if n <= 1: # BASE CASE
3        return 1
4    return n * factorial(n - 1) # RECURSIVE CALL

Recursion and Stack

How does the computer accomplish such a feat as calling a function itself? The answer is quite simple - it uses a stack behind the scene to keep track of where things are. For this particular problem, the factorial recursive function roughly translates to this when executed:

1def factorial_stack(n):
2    stack = []
3    # push each call to a stack
4    # top of the stack is base case
5    while n > 0:
6        stack.append(n)
7        n -= 1
8
9    res = 1
10    # pop and use return value until stack is empty
11    while stack:
12        res *= stack.pop()
13
14    return res

A computer's internal stack is called "call stack" and the data it pushes onto a call stack are called "stack frames". Strictly speaking, stack frames on a call stack represent the function you are calling and its arguments. You can visualize recursive function execution with this handy dandy tool: