Recursion Made Simple: How Two Calls Shape Your Code | binary recursion

 

In recursion, when a function makes two recursive calls within its body, it is referred to as binary recursion. This is because the recursion "branches" into two parts at each step, much like a binary tree.

Binary Recursion: A function that calls itself twice within the recursive case, creating two subproblems for each call. As in your example, the function counter(n) calls counter(n - 1) twice, causing the recursion to branch into two directions.

This leads to a recursive tree with exponential growth, which results in the time complexity of O(2^n), as seen in the image.

Recursion is a fundamental programming technique where a function calls itself to solve smaller instances of the same problem. This image beautifully illustrates how recursion works through a simple counter function that prints numbers, and the recursion unfolds into a tree-like structure. Let’s break it down step by step.

-----

function counter(n) {
    if (n > 0) {
        console.log(n);
        counter(n - 1);
        counter(n - 1);
    }
}

------------------------

Time Complexity and Recursion Tree

The function’s time complexity is O(2^n). This is due to the fact that at each step, the function makes two recursive calls, leading to an exponential growth in the number of function calls as n increases.

The recurrence relation that describes this function is:

$$T(n) = 2 \times T(n-1) + 1$$

Where T(n) represents the total number of function calls at level n. The number of recursive calls doubles at each level of the tree, which leads to exponential growth.

The red lines in the image are used to represent the flow of execution in the recursive function, showing how the function calls branch out and return, which is often referred to as function call tracing.

Here’s what the red lines indicate:

1. Downward Arrows (Function Calls):

• The arrows pointing downward represent recursive function calls.
• Each time the function calls itself (i.e., counter(n - 1)), the flow moves downward, branching into two new recursive calls at each step.
• This branching continues until the base case (n = 0) is reached, where no further calls are made.

2. Upward Arrows (Function Returns):

• The arrows pointing upward represent the return from the recursive calls.
• When the base case is hit (i.e., n = 0), the recursion stops at that particular branch, and the function begins to return back up the call stack.
• As the function unwinds, it backtracks along the same path it followed during the downward calls, thus returning up the tree.

3. Flow of Execution:

• The red lines with arrows visualize how the function moves through each recursive call. They trace how the function goes deeper into recursion (downward), and once it hits the base case, it returns to where it was previously called (upward).
• Example: Starting from f(4), the red arrow shows that the function first moves to f(3), then to f(2), and so on. After reaching f(0), it returns back up to f(1), then continues with the other recursive calls from where it left off.

4. Branching and Backtracking:

• The flow represented by red lines highlights the recursive branching process, where each node creates two subproblems (one left, one right). It also shows the process of backtracking, where once a branch has been fully explored, the function backtracks and explores the other branch.

In essence, these red arrows with lines visually show how recursion navigates the function call stack, moving downward as it makes recursive calls, and backtracking upward as the calls return to their previous state.

Key Terms and Explanation:

1. f(n):

• This represents the function counter(n) at any level of recursion.
• In this example, f(n) is the recursive call counter(n).
• For each n, the function prints the current value n and makes two recursive calls to counter(n-1).

2. Base Case (n = 0):

• The function will stop when n reaches 0, as specified by the condition if (n > 0).
• This is known as the base case, which prevents infinite recursion. Once n = 0, no further recursive calls are made.
• The base case terminates each branch of the recursion tree.

3. Recursive Case (Calling counter(n-1) twice):

• In the recursive case (if (n > 0)), the function makes two recursive calls:
  • counter(n - 1)
  • counter(n - 1)
• Each recursive call creates two new branches, leading to a binary recursion.