0% completed
Introduction to Recursion
Recursion is a powerful problem-solving technique and a fundamental concept in computer science. At its core, recursion occurs when a function (or definition) refers to itself, either directly or indirectly. While it might sound circular or confusing at first, the recursive approach often simplifies complex problems by breaking them down into smaller, more manageable pieces.
What Is Recursion?
Recursion is a method of solving a problem by having a function call itself. Consider a common analogy: standing between two mirrors. You see an image of yourself within the mirror, which in turn shows the mirror behind you, which also shows you, and so on. This “repeating” of images is conceptually similar to what happens in recursion—a function repeatedly calls itself.
Recursion Preliminaries
The term "recursion" is derived from Latin verb "recurrere", which means "to run back". Recurrere is a precise reflection of what recursion does. A recursive solution runs back onto itself, solving a problem by breaking it down into sub-problems of the same nature.
As we proceed to the next sections, we'll translate this concept into computer programming, exploring how functions can call themselves to solve problems. We'll examine the architecture of a recursive function and identify some of the common pitfalls encountered in recursive implementations.
Structure of a recursive function
Understanding the structure of a recursive function is crucial for effective recursive problem-solving. Generally, if a function generates a call to itself in its body, we say it is a recursive function. However, a useful problem-solving recursive function should have well-defined definitions for the following constituents:
- Base case
- Recursive case
- Function prologue and epilogue
Real-Life Analogy
Think of recursion like a set of nested Russian dolls. To get to the innermost doll (the base case), you open each larger doll one at a time (recursive calls). Once you reach the smallest doll, you start putting them back together in reverse order (returning from the recursion).
Let's understand these constituents with easy examples.
The base case
The base case is the condition under which the function stops making further recursive calls. You can consider it as the simplest instance of a problem that can be solved directly.
Let's consider a function that counts down from a given number n, and when it reaches the end, it prints the message 'Happy New Year!'.
In the base case above, if n equals 0, the function prints "Happy new year!".
Important: Always begin by identifying the base case while designing a recursive function. It's the cornerstone that prevents infinite recursion.
The recursive case
It handles the more complex instances of the problem. It further breaks down the problem and calls the function with the reduced problem size.
Continuing with our countdown problem:
Here, if n is not 0, we print n and then call the countdown() with n-1. Hence, all cases where we issue a new countdown() call are recursive cases.
Function prologue and epilogue
The prologue consists of the operations we perform before issuing a new recursive call, and the epilogue includes the operations we perform after the recursive call.
In our countdown example, printing the number n is part of the prologue, and there's no operation in the epilogue.
Be mindful of the operations in the prologue and epilogue. Their order can significantly affect the function's behavior.
Here is the complete working code example running countdown from 10:
Challenge: Update the above countdown() function to have an epilogue instead of a prologue. Then try to figure out what changes in the final output.
Having understood the structure of recursive functions, it's important to note that incorrect implementation can lead to common errors. We'll navigate these potential pitfalls in the next section.
Common mistakes in recursive implementations
Even the most experienced programmers can occasionally stumble when it comes to recursion. It's a powerful tool, but one that requires a cautious approach. Let's examine a few common mistakes.
Infinite recursion
The first, and perhaps most dreaded, pitfall is infinite recursion, where a function calls itself endlessly. This happens when the base case isn't properly defined or reached.
Consider the following recursive function that should decrement a number n until it reaches 0.
The decrementToZero() function will infinitely call itself recursively as recursive case in the base case never makes any progress towards the base case.
Tip: Always ensure your function makes progress towards its base case.
Challenge: Can you modify the decrementToZero() function to ensure it doesn't cause infinite recursion?
Answer: Just decrement n in the recursive call: decrementToZero(n-1).
Ignoring the returned value
Another common oversight is ignoring the value returned by the recursive call, often leading to incorrect results. Here's an example:
In the function above, the n * factorial(n-1) result isn't returned, leading to incorrect outputs.
Challenge: Can you fix the factorial function?
Answer: Add the return statement: return n * factorial(n-1).
Excessive recursion
In the context of recursion, a call stack is a mechanism that keeps track of function calls in a program. It's an important part of recursion because it helps keep track of where the program should return to after a function call is completed.
When a function calls itself (which is what happens in recursion), each call to the function is added to the call stack. This includes the values of any parameters and variables. The program uses the call stack to keep track of these function calls.
Then, when a base case is reached (which is the condition that stops the recursion), the program starts to "unwind" the stack. This means it starts to take function calls off the stack and finish them off one by one, using the variables and parameters values that were stored. This process continues until the stack is empty, which means all the function calls have been completed.*
Since each function call adds a stack frame over the call stack. Thereby, naively underestimating the recursion depth can lead to excessive load on the call stack. Hence, it can overload it - resulting in the stack-overflow exception.
In the upcoming section, we'll explore the concept of the call stack and learn how to represent a recursive function using a recursion tree.
Table of Contents
Introduction to Recursion
What Is Recursion?
Recursion Preliminaries
Structure of a recursive function
Real-Life Analogy
Common mistakes in recursive implementations