Recursion can be a powerful tool. But sometimes we use our tools in a way that ends up hurting our hamsters. In this post, I am going to walk you through the fundamentals of recursion and its use cases.
What is Recursion?
Recursion is a technique used to define a function in terms of itself. It is a way of decomposing a problem into smaller ones. In theory, recursion finds its root in induction. Think about the domain of a function, i.e., the set of all the possible inputs of a function. The domain of a recursive function is usually a set that can be defined inductively.
Know more about how is to work at Intraway from a first-hand Project Manager experience here!
Take, for instance, the recursive factorial function. The factorial of a non-negative integer n, denoted by n!, is the product of all positive integers less than or equal to n. The recursive definition is as follows:
I. factorial(0) = 1
II. factorial(n) = n * factorial(n-1)
Consider the domain of the factorial function, which is the set of positive integers, a.k.a. natural numbers, with the zero. The set of the natural numbers (ℕ) has a definition that is also recursive. It is called an inductive definition:
I. 0 belongs to ℕ
II. If n belongs to ℕ then n+1 belongs to ℕ
Note the relationship between the definition of factorial, and the definition of ℕ:
- Factorial is explicitly defined for zero, in the same way as ℕ.
- Factorial is defined for n and then walks backward – Note that the second clause of the factorial function can be changed to factorial(n+1) = (n+1) * factorial(n) –
It’s worth nothing that we don’t always have functions as easy to implement as factorial(n). In most cases, the functions or algorithms will be much more complicated. Their definition may not match the inductive definition of the set.
But what do we mean by “it does not match the inductive definition of the set”? Another example: The Fibonacci function:
I. fibonacci(0) = 0
II. fibonacci(1) = 1
III. fibonacci(n+2) = fibonacci(n+1) + fibonacci(n)
The factorial function mentioned before uses something called primitive recursion (i.e., the function takes its value based on the value of the previous one). The Fibonacci function does not use primitive recursion. There are specific rules it will have to follow.
- Recursion termination establishes that the algorithm must end somehow, or that the function should have a base case.
- Does Fibonacci end? Yes, when called for 1 or 0.
- Exhaustivity: The function should be well defined for all elements in its domain
- Well, all positive integers greater than 1 are of the form n+1 or n+2.
- Overlapping: Are there any other ways to compute the same value? The Fibonacci function does not overlap (0 ≠ 1 ≠ n+2).
But it does have some caveats…
Superfluous computations
Recursion favors immutability. That concept establishes that the state of an object must remain unaltered with time.
Iterative algorithms will usually change a local variable (a counter, an accumulator, an index, etc.). But a recursive one may not have to. Counters, indexes or accumulators can be passed by value; lists can be iterated using the tail() function, etc.).
Going back to the Fibonacci function, let’s implement both, an iterative and a recursive solution:
So, both functions exit early for n1 to comply with clauses I and II. The iterative function walks from 2 to n and increments an accumulator. Meanwhile, the recursive one calls itself recursively.
Note that the iterative version of the function executes at least n-2 steps. Therefore, it is correct to assume it has linear complexity.
The recursive version calls itself twice on each call. What is the complexity of this case? It is exponential! Yes, the recursive implementation executes 2 nsteps. Why? Let’s run this function step by step for the number 4:
fibonacci(4)
|-- fibonacci(3)
|-- fibonacci(2)
|-- fibonacci(1) -> 1
|-- fibonacci(0) -> 1
|-- fibonacci(1) -> 1
|-- fibonacci(2)
|-- fibonacci(1) -> 1
|-- fibonacci(0) -> 1
The function calls itself twice on each call. The statement above shows that the function was called twice for the number 2, 3 times for 1, and twice for 0. Superfluous calls is a major caveat of recursion and should be avoided. In this case, we jumped from linear complexity, in the iterative version, to exponential complexity, in the recursive version.
The stack problem
The stack is an area of memory used to save the frames of execution and the memory used for local variables. Every time a function is called the stack increases its size. Once the function has ended, the stack goes to its previous state.
Recursive functions make intensive use of the stack. Each recursive call will demand a new frame to be created. Then is pushed onto the stack and, when the recursive call terminates, is removed. Of course, the recursive call could also make recursive calls, and so on…
The stack is a finite resource. Thus, too many function calls will end up exhausting the stack resulting in the termination of the program.
The cost of a function call
Calling a function consumes time and memory. Each time you perform a function call, the CPU will have to perform some extra work. First, the CPU has to save the current state of the program. This step includes saving the content of the Code Segment and Instruction Pointer registers, which are pushed onto the stack.
Then, there is the issue of parameter passing. Depending on the hardware architecture and the calling convention, these are also pushed onto the stack or stored in CPU registers. Using CPU register for parameter passing may imply that those registers are backed-up somehow. And last but not least, the program will jump to the beginning of the function.
After the function ends, all the actions described above must be undone. These actions will also take some time to run!
What can you do to improve the efficiency of our Recursion?
Iterative implementations will usually perform better than recursive ones, but not always. There are also some paradigms and programming languages that promote the use of recursive functions in certain cases.
It is also possible that, with match problems, the solution is broken down into a single formula. Such is the case of Binet’s formula for computing to a Fibonacci number or the sum of the first n integers.
Tail recursion
A tail call is a subroutine call performed as the final action of a procedure. A subroutine is tail-recursive when a tail call leads to the same subroutine that was called again later in the call chain.
This condition allows the so-called tail-call optimization (or tail-call elimination). The tail.call optimization consists of calling the function on the same stack frame used by the function that is about to end. Because the call is the last thing the function will do, the frame is no longer needed, so it’s reused to call the other function.
So, in the end, what it was a recursive function call ends up being some iterative method.
Most functional programming languages (Haskell, Lisp, Scala, Closure) support tail-call optimization. Even Javascript (in its ECMAScript 6 standard) supports it. It is also used by some C++ compilers when enabling certain optimizations.
The following image shows a comparison of the code generated by the compiler with and without optimizations:
The key here is the suppression of the PUSH instruction. PUSH is responsible for growing the stack (Note: In x86 the stack grows downwards from the top of address space).
The Fibonacci function is even more interesting! Both recursive calls make use of the same stack frame. There is also some optimization on the use of CPU registers but that not the point of this article.
Dynamic programming
Dynamic programming is a method that consists of splitting a problem into several smaller issues. I also store the solution to each of those subproblems to re-use it when the same problem occurs. Memoization is this technique of storing solutions to subproblems instead of recomputing them.
The goal of dynamic programming is to save time at the expense of storage space. The storage would hold the solutions to each sub-problem according to the problem being solved.
Going back to our Fibonacci function, there is a way to improve the computation time. By using an array to hold the result of the intermediate problems we can manage time better:
There are tons of algorithms with some recursive behavior. Knowing when and how to implement these algorithms using recursive code is a skill that all programmers should have.
The three properties (termination, exhaustivity, overlap) are key to the success or failure of a recursive algorithm. The programmer must make sure the algorithm finish before exhausting the stack. It has also need to make sure all elements in the domain are taken into consideration. Last but not least, it must ensure there is only one solution for each input.
There are several techniques that can help improve the performance of a recursive implementation. We reviewed two of them: tail-recursion and dynamic programming (a great alternative to greedy algorithms). There is, of course, always the chance to transform the recursion into an iteration, but sometimes that may be too difficult!
Intraway’s Proactive Monitor solution allows CSPs evaluate access services and detect problems before the client perceives them and makes a claim. Know how it works!
