Recursion Theory and Recursive Functions
December 2023 — Hasanain Alsabonchi, Technical Reviewer; Julien Chaffraix.
Recursion theory is a subfield of Computer Science. Almost everything in programming has a mathematical foundation, including sets, functions, arrays, and maps. The mathematical definition of recursion involves defining an object (a function, sequence, or structure) in terms of itself or a part of itself. One such example is factorial. The function f (n−1) represents a subproblem of the original problem f (n), and n - 1 is a step toward reaching the base case. The recursive definition of a recursive function consists of two parts:
A factorial of a number 'N' is the product of all integers between 1 and N. For example, if 'N' equals 5, then the factorial of 'N' would be 5 4 3 2 1, which equals to 120. A recursive definition can be used to solve a problem mathematically or programmatically. The factorial function 'Fact(n)' can be defined recursively as follows:
For instance:
f (5) = 5 * f (4)
f (4) = 4 * f (3)
f (3) = 3 *f (2)
f (2) = 2 *f (1)
f (1) = 1 * f (0) (where f (0) = 1)
The Fibonacci sequence is a good example of a recursive relation with two base cases.
For instance, to find the 4th Fibonacci term:
f (0) = 0
f (1) = 1
f (2) = f(0) + f (1) ⇒ 1
f (3) = f(2) +f (1) ⇒ 2
The base case serves as a way to break out of the recursion. A recursive function should reach and execute one or more base cases to avoid infinite recursion. For tree problems, you might see 'if (node == null) return,' which is a typical base case. The recursive step, on the other hand, is where a function calls itself with a typically smaller input size/value and utilizes the result of the recursive call to help solve the current problem. It can involve multiple recursive calls, as seen in problems like the Fibonacci sequence.
Having explored recursion, let's now examine and contrast recursive algorithms with their iterative counterparts.
Recursion vs. Iterative Programming
Recursion allows solving complex programming tasks concisely. Inversely, an iterative approach is less concise as we repeat a single statement or a block of statements a certain number of times or until a specific condition is met. The Church-Turing thesis proves that what is computable by a recursive function is computable by an iterative one and vice versa. This is because recursion can be implemented using loops and a stack. Recursive algorithms have a space complexity, specifically in non-tail recursion, which is directly related to the maximum depth of the function call stack during execution. However, the iterative approach typically has no associated space complexity unless it adds an extra stack. The following code computes n! (n factorial) using two different approaches
One important component of recursion is the stack. Let’s look at how the stack is managed.
Recommended by LinkedIn
Stack Memory Management
When an operating system (OS) runs a program, the loader first loads the program’s data and code into the main memory. This enables the CPU to access and execute the program's instructions and work with its data. The stack plays a central role in managing a program's execution. One crucial component of stack memory operations is the Stack Pointer (SP), a CPU register that indicates the top of the stack, The Stack Pointer is automatically adjusted each time a stack operation is executed. The stack memory is pre-allocated at program start because, by definition, it must be contiguous in memory. This also means that the stack memory is fixed throughout the lifetime of the program.
Stack Register
'ebp’ and ‘esp’ are x86 architecture registers used to manage the stack. ‘esp’ is the stack pointer, used to manage the stack. It is adjusted to allocate space for local variables and to pass arguments to functions. ‘ebp’ is the base pointer, keeping track of the start of the current stack frame. It is sometimes used to access parameters and local variables. Now, let's examine the following recursive program.
Inside 'foo()', just before calling 'bar()', we need to pass two arguments to the function. This is accomplished by pushing them onto the stack, as illustrated in Figure 1. The CPU is only aware of the next instruction to execute, stored in a register known as the Instruction Pointer (IP). To return from a function call, we must save the next instruction to be executed after the call. Therefore, this instruction is pushed to the stack in Figure 2, just before calling 'bar()' (the call is achieved by updating IP to the beginning of the function ‘bar()’).
Upon returning from 'bar()', the program must revert the frame to the state as it was in Figure 1 (this operation is referred to as "unwinding" the stack). To achieve this, we save the stack base pointer (ebp) in the stack, just before updating it for the new function. When returning, the compiler will generate code that resets the stack pointer (esp) to the current ebp and then restores the previously pushed ebp. Figure 3 represents the code immediately after saving the caller’s ebp.
Finally, the two variables, 'x' and 'y' in 'bar()', are pushed to the stack, as shown in Figure 4.
Each programming language has its distinct calling convention and is designed to work with various platforms (CPU architecture + operating system). Understanding the call stack is fundamental when working with function calls and recursion. When a function is called, whether it's a normal function call or a recursive call, the program's execution environment creates a new stack frame (also known as an activation record). This stack frame contains information such as local variables, function parameters, and the return address. Since it operates on the Last In, First Out (LIFO) principle, storing data on the stack is called 'pushing' (using the PUSH instruction in x86 assembly), and restoring data from the stack is called 'popping' (using the POP instruction). These operations are common in assembly or low-level languages.
In the case of recursive functions, each recursive call creates a new stack frame on top of the previous one. The call stack ensures that the program can keep track of its execution flow and return to the appropriate caller after a function completes its task.
When a function encounters a return statement or throws an exception, it exits the current recursive routine with its current inputs. As the function completes its execution, this information is popped from the stack.
Tree problems are a type of problems that can be solved neatly using recursion. Let's look at one final example to see how the stack gets updated.
The problem we’re looking at is whether a tree is balanced. This is the LeetCode exercise if you’re curious. A common solution is to recurse on each subtree and track whether each subtree is balanced. If one subtree is unbalanced, we can propagate the information up to the root (which is modeled as the magic constant -1 in the following code snippets):
Here is an example of the function calls involved and their return values:
Now if we look at the hardware stack, the following diagram shows the different states that it will go through as we invoke ‘height’. The sequence is similar to the previous example above pushing the return address, then the previous 'ebp' then any arguments, and finally the local variable.
In summary, recursion is a powerful programming technique, often used for tasks like calculating factorials. It differs from iterative approaches but can achieve the same results. However, recursion can be space-inefficient. Stack memory is crucial in program execution, especially in tracking function calls and recursion. Understanding the call stack and its management is essential for programmers. Recursion, while elegant, can be challenging to master.
¹ Stackoverflow Can every recursion be converted into iteration?
² Tail Recursion Tail Call
³ Calling Convention https://en.wikipedia.org/wiki/Calling_convention¥
Thank you for bringing this to my attention. fixed
You might want to correct the recursive function to calculate factorials. The if statement needs to check for n<=0 instead of n<0. Otherwise it will return 0 for every positive number. :D