- What is Recursive Function
- Compare Recursion to Iteration (loops)
- Understand Stack Unwinding in Recursion
🌀 Introduction to Recursive Functions
Let's look at recursive functions in Python.
A Recursive Function is a function that can call itself over and over to solve a smaller piece of the same problem until it reaches the base case (It's like stop condition).
Technically, you can achieve the same result with loops, but sometimes recursive functions can make your code simpler to read and allow to express certain algorithms much better.
Also, keep in mind that to understand Recursive Functions, you need to know 4 things:
🔹Base Case
🔹Recursive Case
🔹Call Stack
🔹Unwinding The Stack
We'll cover all of them in a moment but first let's compare Recursion Syntax to While Loops so you can better understand how it works.
Let's dive in
🔁 Loops vs. Recursion
Let's create a simple function to countdown from a given number. (5,4,3,2,1,0)
There are many ways to do that, but I want to compare while-loop and recursive solutions because they have the closest syntax to help you better understand it.
🅰️ Countdown - While Loop
If we decide to use While loop it's all about creating the right condition to stop its execution.
Also it's possible to simplify this syntax even more, but I wrote it like that for a reason.
Here's the code:
Let's briefly break it down:
We create infinite loop with
while True:We create break-condition to wait until
nbecomes less than 0if n<0: breakWe
print(n)and decrement its value(n-=1)until we hit the break statement.
It's a very straight-forward solution.
🅱️Countdown - Recursive
Now let's how to achieve the same with Recursive. You'll notice that it has a lot of similarities with the first code snippet.
Let's break it down:
First of all we define a Base Case. It's like a break-condition in while loops. This is how we specify the end condition to avoid infinite recursion (
limit is 1000).If your current argument isn't reaching Base Case then it goes to Recursive Case where it can call itself with a little different arguments.
So this function will call itself until it reaches the base case like this:
countdown(5) ➡️ countdown(4) ➡️ countdown(3) ➡️ countdown(2) ➡️ countdown(1) ➡️ countdown(0)
👆This is the Call Stack.
We call the same function over and over and we stack them on top of each other. And then when the Base Case condition is reached, we've reached the end and we're going to start to Unwind the Stack to get to the final result. (More on that later)
⛔In our case, we're not returning anything, we just print(n) . So we don't really Unwind The Stack, but I'll show you code example with the unwinding part in a moment.
Let's keep it simple for now.
🅱️ Important Recursive Definitions
So, let's focus on the key terms of Recursive Functions:
🔷BASE CASE - is the stopping condition in recursion that prevents infinite calls. (Similar to break-condition in while loops)
🔷RECURSIVE CASE - is the part of a recursive function where it calls itself again with a smaller or simpler problem until it reaches the base case.
🔷CALL STACK - Is a chain of function calls that happen during the recursion when it calls itself until reaches the base case.
🔷UNWINDING THE STACK - is the process where after reaching the base case, the recursive calls start returning results one after another in a chain until reaches the final result to the first function call.
💡 It's okay if these terms are still not 100% clear. You'll better understand them with the factorial example that we'll create next. I just wanted to cover them in advance so you know what to expect.
⭐ Recursive Function - Factorial Example
Let's look at a better example for Recursive Function such as - Factorial.
If you're not familiar:
💡 Factorial is the product of all numbers from 1 to n.
Examples:
Factorial 3! = 3 × 2 × 1 = 6
Factorial 4! = 4 × 3 × 2 × 1 = 24
Factorial 5! = 5 × 4 × 3 × 2 × 1 = 120
This is a classic example for recursion because it naturally breaks down into smaller subproblems where final results depends on the previous ones.
To begin with, I'm again going to provide 2 solutions for While loop and Recursive to compare, and then we'll dive deep into recursive and I'll break down everything that's happening under the hood.
🅰️While Loop:
This one is quite simple:
- Define default value (1)
- Create Break Condition n <= 0
- Modify n to Calculate Factorial Result
Now let's look at the Recursive Function:
First of all, can we appreciate how much cleaner the syntax. Now let's get into it.
🔹Firstly we define the Base Case for the default value if n<=0
🔹 Then we create Recursive Case to keep calling the function as we decrease n
🔹 While we keep calling the function - we're creating a Call Stack➡️factorial(3) ➡️factorial(2) ➡️factorial(1) ➡️factorial(0)
🔹 Once we reach the Base Case (n=0) it stopps to create recursive calls, and instead it begin to Unwind The Stack. This means that we're going in the opposite direction and we are bringing results from the last call to the first one to calculate the final result.
Let me illustrate this point, THIS IS IMPORTANT:
You can see the Call Stack of factorial(5) ➡️ factorial(0) , and then once you reach the top (base case) it starts to calculate results in reverse order, because it needs it to calculate the previous function call.
Therefore when we run factorial(5) we'll get 120
Look Behind The Curtain
Lastly, let's modify the factorial function by adding print statements so you better understand the flow of how it calculates it. This part will teach you the most.
So here's update code, and I'm just adding print statements:
So now we can run factorial(5) and we can track each iteration and step in the process.
This result is not what majority of you expected but let's break it down.
1️⃣ Creating Call Stack
So we're starting with factorial(5). First of all it will print the n value and then since we're not hitting the base case it will more to result= n * factorial(n-1) line to go one layer deeper into Recursive case.
Therefore we can see print statements Entering Factorial: 5,4,3,2,1,0
💡 At this point, no return statements were executed!
2️⃣ Reaching Base Case
Eventually we'll get to n<=0 and it will trigger the Base Case.
At means that we've reached the end of the stack and we're executing the first return statement.
After this point, we're going to begin Unwinding The Stack.
3️⃣ Unwinding The Stack
No we're going in the opposite direction and each call will get to the return point and pass it to the previous call. This is all necessary to reach the final result of the very first call (factorial(5))
Look at this doodle:
This is our Stack Call, and we're starting at the bottom and keep creating more calls until we reach the Base Case. Then we're moving in the opposite direction and provide answers for each.
That's how we get to Result = 120 .
That's the basics of Recursive Function.
📌 When to Use Recursion?
Now you probably wonder - When to use Recursive Functions?
Honestly, as a beginner you won't use it.
It's good to know that it exists and how it works, but it's a hard concept to grasp on the very first try. And it will much often be simpler to use while-loops to achieve the same result, even if your code gets a bit longer.
Recursion is useful when a problem can naturally be broken down into smaller versions of itself.
It's commonly used for:
🔹Math algorithms (Factorial, Fibonacci...).
🔹Working with nested structures (Folders, JSON, Trees...).
🔹Searching and Sorting algorithms.
🔹Puzzles where you need to explore multiple possibilities.
If you want challenge - I have a very simple exercise for you.
👉 Create a recursive function that takes a number and sums its digits until you’re left with a single digit. (see image below)
🤔 Hints:
Base Case: If the number has only one digit, return it.
Recursive Case: Sum all digits, then call the function again.You can solve this with loops, but recursion makes it a fun exercise.
Use this to begin your code:
‼️PS.
The answer is in the end of the video lesson.
But try it yourself first!
Sposored by LearnRevitAPI.com