??Recursion

Recursion is a programming technique where a function calls itself to solve smaller instances of the same problem until it reaches a base condition that stops the recursion. It is particularly useful for tasks that can be broken down into repetitive or similar sub-tasks.

In the example above, the countdown() function prints numbers from 5 to 1 and stops when n becomes 0. The function repeatedly calls itself, reducing the number by 1, until the base condition n <= 0 is met.

??? What is base condition?

The base condition (or base case) in recursion is a condition that defines when the recursive calls should stop. It prevents infinite recursion by providing a clear stopping point. Without a base condition, the function would keep calling itself indefinitely, leading to a stack overflow or memory exhaustion. We will learn about stack overflow in upcoming article.

In simpler terms, the base condition is the scenario where the problem becomes simple enough to be solved directly, without further recursive calls.

Example Explained: The Recursion in Action

Consider this code:

This is not a typical example of recursion since no function is directly calling itself. However, the structure of the calls can be viewed as a recursive-like chain because each function is calling another function that eventually reaches the bottom of the chain.

Here’s how it works:

• grandFather() calls father().
• father() calls son().
• son() completes the chain by printing "Son".

What is a Recursion Tree?

A recursion tree is a diagrammatic representation used to visualize the recursive calls of a function. Each node represents a function call, and the child nodes represent further recursive calls made from the parent. The tree grows as the function calls itself, and eventually, the leaves represent base cases, where the recursion stops.

For example, the recursion tree for a Fibonacci series looks like this:

How the Arrow Flow Works:

The arrows in the recursion tree represent the flow of recursive calls and the return of values. Here's a step-by-step explanation:

1. Starting Point: fib(5):
2. Recursive Breakdown:
3. Base Cases: fib(1) and fib(0):
4. Return Values (Going Up the Tree):
5. Returning to fib(5):

This tree shows how the Fibonacci function recursively breaks down the problem into smaller sub-problems.

How is Recursion Data Stored in Memory?

Recursion uses a data structure called the call stack. Every time a recursive function is called, a new frame (or instance) is added to the stack. This frame holds the function’s variables and its place in execution. When a function reaches its base case and starts returning, its frame is removed from the stack.

For instance, in the countdown(5) example, the memory stack looks like this during execution:

1. countdown(5) is called, frame for n = 5 is pushed onto the stack.
2. countdown(4) is called, frame for n = 4 is pushed.
3. This continues until countdown(0) where the recursion ends.
4. Then, the frames are popped from the stack as the function returns back up.

?? Thanks for reading this article. The next few articles will cover how array methods work internally using DSA concepts.