Lesson 5

Greetings, coder!

Today, we're unraveling the world of **recursion**. Recursion is a scenario in which a function calls itself. Think of Russian Matryoshka dolls -- each doll contains a smaller doll inside, which mirrors the concept of recursion.

Recursion is valuable when you can break down a problem into smaller, yet similar, simpler problems. It plays a critical role in various tasks such as sorting and searching algorithms.

The lesson for today involves understanding recursion, implementing it in `C++`

, comparing it with iteration, and practicing debugging it.

Recursion in programming occurs when a function solves a problem by resolving smaller instances of the same problem. This is akin to tracing a family tree -- each person reports their parent, who, in turn, does the same. This process of lineage tracing serves as a good metaphor for recursion.

However, it is paramount to define a proper base case in recursion to bring it to an end and avoid infinite loops.

Now, we will examine recursion in `C++`

using factorials as an example. The factorial of `n`

is `n`

times the factorial of `n-1`

.

Here is the `C++`

implementation:

C++`1#include <iostream> 2 3int factorial(int n) { 4 // Base case: 5 if (n == 1) { 6 return 1; 7 } 8 // Recursive case: 9 return n * factorial(n - 1); 10}`

In the implementation above, the function `factorial()`

calls itself to compute the factorial of `n`

. Here is the key things to pay attention to:

**Base Case**

Within the `factorial`

function, the base case is checked first. The base case is the condition under which the function stops calling itself. If `n`

is 1, the function returns 1. This prevents infinite recursion and serves as the termination condition.

**Recursive Case**

If `n`

is not 1, the function proceeds to the recursive case. It returns `n`

multiplied by the result of `factorial(n - 1)`

. This means the function calls itself with `n`

reduced by 1, breaking down the problem into smaller subproblems until it reaches the base case.

Here is how we can call our recursive function:

C++`1int main() { 2 // The factorial of 5 is 120: 3 std::cout << "The factorial of 5 is: " << factorial(5); 4 return 0; 5}`

The result of `factorial(5)`

is calculated as `5 * 4 * 3 * 2 * 1`

, which equals 120. In our program, it works in the following way:

- We call the
`factorial(5)`

, starting the recursion - The result of the
`factorial(5)`

is`5 * factorial(4)`

according to the function's recursive case - The result of the
`factorial(4)`

is`4 * factorial(3)`

. Overall, the result of the function at this point is`5 * 4 * factorial(3)`

- Similarly, we get to
`5 * 4 * 3 * 2 * factorial(1)`

. The`factorial(1)`

call triggers the base case and returns simply`1`

. Thus, the overall return value is`5 * 4 * 3 * 2 * 1`

, which is our correct answer.

While recursion simplifies code, it can consume more memory than iteration. Iterative solutions might seem more complex at glance, but they are more efficient. For instance, we can use a `for`

loop to calculate the factorial:

C++`1#include <iostream> 2 3int factorial(int n) { 4 int result = 1; 5 // Loop through numbers from 1 to n: 6 for (int i = 1; i <= n; i++) { 7 // Each time, multiply the result by the current number: 8 result *= i; 9 } 10 return result; 11} 12 13int main() { 14 // The factorial of 5 is 120 (the same as with the recursive method): 15 std::cout << "The factorial of 5 is: " << factorial(5); 16 return 0; 17}`

Defining a base case for ending recursion is crucial. Without a properly defined base case, you might find yourself in an endless loop.

Let's see what happens when a base case isn't defined:

C++`1#include <iostream> 2 3int factorial(int n) { 4 return n * factorial(n - 1); 5} 6 7int main() { 8 // Recursion doesn't stop, causing a stack overflow error: 9 std::cout << "The factorial of 5 is: " << factorial(5); 10 return 0; 11}`

This code results in a runtime error due to a stack overflow as `factorial()`

calls itself indefinitely, thus causing infinite recursion.

When dealing with recursion, understanding the call stack is essential. In `C++`

, when a function calls itself, each call is added to the stack. Once the base case is reached, the calls start returning until no calls are left in the stack. This process is known as "backtracking."

This is precisely why recursive functions may consume more memory than iterative ones, possibly leading to a stack overflow.

Learning recursion involves the possibility of making mistakes such as forgetting the base case or making a recursive call that doesn't progress towards it.

When debugging recursive functions, start with small inputs and use `std::cout`

statements at critical junctures to keep track of variable values and state changes.

Congratulations! You've learned about recursion, its functioning in `C++`

, the differences between recursion and iteration, and debugging recursive functions.

Now, it's time to practice these concepts to consolidate what you've learned and understand how they work in different scenarios.