Recursion: Behind the Scenes

Welcome to Recursion!

---

Hi! Welcome to this introduction to recursion, it’s great to have you here. 😀 This is a very powerful concept in programming… a function that calls itself! I know what you must be thinking: What?! The function calls itself? Why would you want to do that? 😅

Recursion is used when the result of a problem depends on the result of smaller versions of the same problem. Sounds strange? Don't worry! You will learn what it means with this tutorial. 😀

Let’s dive into the details with an example, calculating factorial.

Meet Factorial 👋

---

The factorial of a positive integer n is the result multiplying all the integers less than or equal to n. For example, the factorial of 3 is 3 * 2 * 1 (by convention, the factorial of 0 is 1) Factorial is denoted as n! in mathematics.

This is the code we will be working with. Please take a moment to analyze it.

---

Base Case

I’m sure that you noticed that there is a call to factorial within the definition of the function itself. (please see the diagram below).

You might think, won’t this cause an infinite loop? 😫

Well, it won’t because we have what it’s called a base case, and we update the argument every time we call the function. The base case is when you specify a value that will be returned when a condition is met, and no more function calls will be made. In this example, when n is 0 or 1, the value 1 will be returned, and no more function calls will be made.

💡 Note: It's very important to update the argument with each recursive function call. In this case, factorial(n-1) is calling the same function but with the argument reduced by 1 each time. This way, we guarantee that the argument will eventually reach our base case, 1 or 0.

---

---

Behind the Scenes?

But what happens behind the scenes when the function calls itself? Let’s say that you call the factorial function with 3 as the argument (illustrated below).

---

---

If statement

The if condition will be checked. If n is either 0 or 1, the integer 1 will be returned. Since this is not the case, the else clause is executed.

---

---

Else is Executed

In this else clause, you see a return statement in which the parameter n is multiplied by the result of calling a function. But in this case, the function calls itself.

---

---

Let's see the process behind the scenes! 🎉

Let’s imagine what happens behind the scenes for a moment. Since n is the parameter, and 3 was passed as the argument, let’s replace the value to illustrate what happens. We now have a function call with a new argument, n – 1. (in this case, 3-1 = 2).

---

---

Once this function call is executed, the program “waits” for the sequence of function calls to complete.

When the function is called within this function with n-1 as the new argument, you need to find the value returned by this new function call before returning a value. Otherwise, how would the computer know what value to return if the expression 3 * factorial(3-1) is not complete? We don’t know the value of factorial(3-1) yet.

As you can see in the diagram below, the program “waits” until a value is returned.

But what happens while the program “waits”?

---

---

The function call to factorial(n-1) is equivalent to factorial(2) because the argument for n was 3. This calls the function again. The if condition is checked with n = 2 as the argument. Since 2 is not 0 or 1, the else clause is executed, and factorial(n-1) is called again, factorial(1). (please see factorial(2) in the diagram below).

The program needs to wait again until a value for factorial(1) is found. The function call factorial(1) is executed, and the value 1 is returned.

---

---

This is the sequence of return statements that are executed during the process. It continues until we reach the base case, when n is either 1 or 0. When the condition evaluates to True, the integer 1 is returned.

---

---

Once a value is returned, those spots that were “waiting” for a result are filled up the chain.

---

---

When the final function call returns a value, 1, that value is returned to the function call factorial(2) and the resulting value, 2, is returned to the first function call factorial(3).

---

---

Finally, 6 is returned from the function call factorial(3)

---

---

This is the code and the final result, 6. I added print statements to illustrate the process. 👍

---

---

I really hope that this has been helpful. If you have any questions, please do not hesitate to ask. Your classmates and Community TAs will always be there to help you. 🙂

Estefania.