Recursion is a technique in computer programming where a function calls itself repeatedly until a certain condition is met. This technique is commonly used in solving problems that can be broken down into smaller, simpler instances of the same problem. Recursion can be a powerful tool, but it can also be tricky to understand. In this article, we will explore how recursion works, how it uses the stack, recurrence relation, and time complexity of recursion, and how static and global variables work in recursion.
In this article of Recursion Part2, we are going to cover topics like: How Recursion Works ( Tracing ), How Recursion uses Stack, Recurrence Relation – Time Complexity of Recursion Static and Global Variables in Recursion.
How Recursion Works (Tracing)
Recursion works by breaking down a problem into smaller subproblems and solving them recursively. The recursion starts with a base case, which is the simplest instance of the problem that can be solved directly. The base case is the stopping condition for the recursion. The recursive function then calls itself with smaller subproblems until the base case is reached.
To understand recursion, let’s take a look at a simple example of the factorial function:
int factorial(int n) {
if (n == 0) {
return 1;
} else {
return n * factorial(n - 1);
}
}The factorial function calculates the factorial of a given integer n, which is defined as the product of all positive integers less than or equal to n. The base case of the factorial function is when n is equal to 0, in which case the function returns 1. For any other value of n, the function calls itself with a smaller subproblem n - 1, until the base case is reached.
Let’s trace the execution of the factorial function with an input value of 4:
factorial(4)
4 * factorial(3)
4 * 3 * factorial(2)
4 * 3 * 2 * factorial(1)
4 * 3 * 2 * 1 * factorial(0)
4 * 3 * 2 * 1 * 1
24
As we can see from the trace, the factorial function calls itself recursively with smaller subproblems until the base case is reached. The intermediate results are stored on the call stack, which we will discuss in the next section.
How Recursion Uses the Stack
Recursion uses the call stack to store intermediate results and to keep track of where to return to after each function call. Each time a function is called, a new frame is added to the call stack. The frame contains information about the function call, such as the arguments passed and the return address.
When a function returns, its frame is removed from the call stack, and the control returns to the caller. The intermediate results are propagated back up the call stack until the original caller receives the final result.
In the example of the factorial function, each recursive call creates a new frame on the call stack, which stores the intermediate result of the multiplication. When the base case is reached, the intermediate results are propagated back up the call stack, and the final result is returned to the original caller.
Recurrence Relation and Time Complexity of Recursion
The recurrence relation is a mathematical formula that describes the time complexity of a recursive function. The recurrence relation for the factorial function can be written as:
T(n) = T(n-1) + O(1)
where T(n) is the time taken to compute the factorial of n, and O(1) represents the time taken to perform the multiplication operation. The base case of the factorial function takes constant time, so we can write the recurrence relation for the base case as:
T(0) = O(1)
Using the recurrence relation, we can calculate the time complexity of the factorial function. By recursively substituting T(n-1) with the recurrence relation, we get:
T(n) = T(n-1) + O(1)
= T(n-2) + O(1) + O(1)
= T(n-3) + O(1) + O(1) + O(1)
= ...
= T(0) + O(1) + O(1) + ... + O(1)
= O(n)
Therefore, the time complexity of the factorial function is O(n), which means that the time taken to compute the factorial of a given integer n is proportional to n.
Static and Global Variables in Recursion
Static and global variables in recursion work differently from local variables. Local variables are created and destroyed every time a function is called and returned, respectively. However, static and global variables retain their values across function calls.
Static variables are declared inside a function with the static keyword. They are initialized only once, and their values are preserved across function calls. Global variables, on the other hand, are declared outside any function and are accessible from all functions in the program.
Static and global variables can be useful in recursion when we want to maintain some state across function calls. For example, let’s consider the following recursive function that calculates the nth Fibonacci number:
int fibonacci(int n) {
static int memo[1000] = {0};
if (n == 0 || n == 1) {
return n;
} else if (memo[n] != 0) {
return memo[n];
} else {
memo[n] = fibonacci(n - 1) + fibonacci(n - 2);
return memo[n];
}
}
the recurrence relation, we get:
scssCopy codeT(n) = T(n-1) + O(1)
= T(n-2) + O(1) + O(1)
= T(n-3) + O(1) + O(1) + O(1)
= ...
= T(0) + O(1) + O(1) + ... + O(1)
= O(n)
Therefore, the time complexity of the factorial function is O(n), which means that the time taken to compute the factorial of a given integer n is proportional to n.
Static and Global Variables in Recursion
Static and global variables in recursion work differently from local variables. Local variables are created and destroyed every time a function is called and returned, respectively. However, static and global variables retain their values across function calls.
Static variables are declared inside a function with the static keyword. They are initialized only once, and their values are preserved across function calls. Global variables, on the other hand, are declared outside any function and are accessible from all functions in the program.
Static and global variables can be useful in recursion when we want to maintain some state across function calls. For example, let’s consider the following recursive function that calculates the nth Fibonacci number:
scssCopy codeint fibonacci(int n) {
static int memo[1000] = {0};
if (n == 0 || n == 1) {
return n;
} else if (memo[n] != 0) {
return memo[n];
} else {
memo[n] = fibonacci(n - 1) + fibonacci(n - 2);
return memo[n];
}
}
The Fibonacci sequence is a sequence of numbers in which each number is the sum of the two preceding ones. The base cases of the Fibonacci function are when n is 0 or 1, in which case the function returns n. For any other value of n, the function calls itself recursively with smaller subproblems n-1 and n-2.
To avoid redundant computations, we can use a static array memo to store the intermediate results of the Fibonacci function. The memo array is initialized with zeros and is used to store the result of the nth Fibonacci number when it is computed for the first time. Subsequent calls to the function with the same value of n will retrieve the result from the memo array, which saves computation time.
Conclusion
Recursion is a powerful technique in computer programming that can be used to solve problems that can be broken down into smaller subproblems. Recursion works by calling a function repeatedly with smaller subproblems until a base case is reached. Recursion uses the call stack to store intermediate results and to keep track of where to return to after each function call. Recurrence relation is a mathematical formula that describes the time complexity of a recursive function. Static and global variables in recursion retain their values across function calls and can be useful in maintaining state across function calls.
