Recursive Functions: Tracing and Recurrence Relations

The Essence of Recursion

At its heart, recursion is a process where a function solves a problem by calling itself with a "smaller" version of the same problem. This process continues until the problem becomes so simple that it can be solved directly, without any further recursion.

This implies that every well-formed recursive function must have two key components:

1. Base Case: A condition under which the function does not call itself again. This is the terminating condition that prevents infinite recursion. Without a base case, a recursive function would run forever, eventually causing a "stack overflow" error.
2. Recursive Step: The part of the function where it calls itself, but with modified arguments that move it closer to the base case. This is where the problem is broken down into a smaller piece.

Let's see a formal definition and a simple code example.

Visualizing Recursion with the Call Stack

How does a computer keep track of all these nested function calls? The answer lies in the call stack, which we discussed in our previous lesson. Every time a function is called—even if it's the same function calling itself—a new stack frame (or activation record) is pushed onto the stack. This frame contains the function's parameters, local variables, and the return address.

When a function reaches its base case and returns a value, its stack frame is popped off the stack, and control returns to the caller (which is the previous instance of the same function). This "winding" and "unwinding" process is fundamental to how recursion works.

The following video provides an excellent, step-by-step visualization of this process. It traces a simple recursive function, showing exactly how the stack grows and shrinks.

As you can see, the call stack is the underlying mechanism that makes recursion possible. Each instance of the function fun has its own private copy of the variable n, stored in its unique stack frame.

A Practical Method for Tracing Recursion

While drawing a full call stack is great for understanding the concept, it can be too slow during an exam like GATE. You need a faster method to trace the execution and find the output. A common technique is to create a "call tree" or a chain of substitutions.

You start with the initial call and write down what it returns in terms of its recursive call. You then expand that recursive call, and so on, until you hit the base case. Once the base case returns a concrete value, you substitute it back up the chain.

The same Neso Academy video demonstrates this exact technique, which is a must-know for solving GATE problems efficiently.

This method is much quicker and less error-prone under time pressure. Practice this technique until it becomes second nature.

Deriving Recurrence Relations

Now we move to the second goal of our lesson: analyzing the cost of a recursive function. In algorithm analysis, we often express the time complexity of a recursive function using a recurrence relation.

A recurrence relation is an equation that defines a function in terms of its value on smaller inputs. For a recursive algorithm, it typically looks like this:

$T(n)=(\text{Time for work done in the current call})+(\text{Time for recursive calls})$

Let's derive the recurrence relation for the time complexity of the function fun(n) we've been analyzing:

int fun(int n) {
    if (n == 1) {       // Base case: constant time work (c1)
        return 1;
    } else {
        return 1 + fun(n - 1); // Constant time work (c2) + recursive call
    }
}

Let $T(n)$ be the time taken by fun(n).

1. Base Case: If $n=1$, the function performs a comparison and returns. This takes constant time. So, $T(1)=c_1$, which we can simplify to $O(1)$.
2. Recursive Step: If $n>1$, the function performs a comparison, a subtraction, an addition, and then makes a recursive call to fun(n-1). The work done within the current call (comparison, subtraction, addition) is constant, let's call it $c_2$, or $O(1)$. The recursive call takes $T(n-1)$ time.

Therefore, the total time $T(n)$ is the sum of the constant work and the time for the recursive call:

$T(n)=T(n-1)+O(1)$

Or more simply, $T(n)=T(n-1)+1$, assuming one unit of time for the constant work. The base case is $T(1)=1$. This recurrence relation precisely describes the time complexity of our function.

The following video from Abdul Bari, a well-known educator in the GATE community, explains this derivation process for this exact type of recurrence.

Solving these recurrence relations to get a closed-form solution (e.g., $O(n)$) is a topic we will cover in depth in the Algorithms module, particularly with the Master Theorem. For now, the crucial skill is being able to derive the relation itself.

Conclusion

Today, we've unraveled the concept of recursion, a cornerstone of computer science. You now have the tools to understand and analyze recursive functions, which will appear frequently in GATE, especially in Data Structures, Algorithms, and Theory of Computation.

Key Takeaways:

• Recursive Structure: Every valid recursive function must have a base case to stop the recursion and a recursive step that moves the problem toward the base case.
• The Call Stack: The call stack is the mechanism that manages recursive calls, with each call getting its own stack frame for local variables and parameters.
• Tracing Execution: You can trace recursion by visualizing the call stack or by using the more practical substitution method of writing out the call chain and back-substituting the results from the base case.
• Recurrence Relations: These are mathematical equations that describe the time complexity of a recursive algorithm. We derived our first one: $T(n)=T(n-1)+1$, for a function that reduces the problem size by one at each step.

In our next lesson, we will explore more advanced recursion patterns that are common in GATE questions. We'll look at tree recursion, tail recursion, and see how to analyze the time and space complexity of more complex recursive code snippets. We'll also get our first look at memoization, a technique to optimize recursive algorithms by storing the results of expensive function calls.