Recursion

Recursion defined

On a functional level, this definition suits adequately:

“Recursion occurs when a function calls itself directly or indirectly”

~https://www.ibm.com/developerworks/library/l-recurs/index.html

Using this basis alone helped me devise functions that recursed, that is, they called themselves. But without further understanding about additional necessary conditions that make them useful, my recursive functions would call themselves indefinitely and not yield solutions to problems.

Consider the following Python script, which has a recursive function that will print a number, and then call itself, passing in the same number:

def print_num(number):
    print(number)
    return print_num(number)print_num(5)

If it could run, it would output 5 indefinitely:

5
5
5
5
5
...

The print_num function is indeed recursive since it calls itself, but printing the same number infinitely is not particularly useful.

Recursive Case

The concept of the recursive case is crucial towards developing useful recursive functions. A function that calls itself with the same parameters will just lead to an infinite state of sameness as we saw in the previous example. A key component of useful recursive functions is that the function call itself with different parameters — the recursive case.

Consider our print number function, only this time, in the call to the function, we will decrease the parameter by one in each call.

def print_desc(number):
    print(number)
    return print_desc(number - 1)print_desc(5)

It will output:

5
4
3
2
1
0
-1
...

This function, now does something more useful — it prints numbers in descending order. However, it will still call itself recursively without end, resulting in output that prints an ever decreasing stream of numbers.

Base Case

The last component of a useful recursive function is the base case. The base case is a condition which a function can return the result without another call to itself. It is the condition at which the recursive calls will terminate, and yield a function that will not produce endless output.

Consider the script below, building upon our previous script that prints descending numbers, with the addition of a base case that will instruct the function to return immediately when the number reaches 2:

def print_desc_until_2(number):
    print(number)
    if number == 2:
        return
    return print_desc_until_2(number - 1)print_desc_until_2(5)

Output:

5
4
3
2

Call Stack

However, with more complex recursive functions, behaviors that can’t be easily interpreted from reviewing the source code alone emerges. Note the following example of a recursive C function which returns the power of two integers passed in as parameters:

#include <stdio.h>int _pow_recursion(int x, int y)
{
        if (y < 0)
        {
                return (-1);
        }
        if (y == 0)
        {
                return (1);
        }
        return (_pow_recursion(x, y - 1) * x);
}int main(void)
{
        int result;        result = _pow_recursion(3, 3);
        printf("result is: %d\n", result);
        return (0);
}

The output will be the result of 3 raised to the power of 3:

result is: 27

Notice there is both a base case to terminate the function calls, and a functional recursive case, which decreases the exponent value each time the function is called. See the commented function below:

int _pow_recursion(int x, int y)
{
/*Checks for negative exponents, this function returns -1 */
        if (y < 0)
        {
                return (-1);
        }
/*Base case, when the exponent reaches 0, return*/
        if (y == 0)
        {
                return (1);
        }
/*Recursive case, call the function again, decreasing the exponent*/
        return (_pow_recursion(x, y - 1) * x);
}

However, to follow the execution of this program, one has to understand the flow of the call stack. The call stack is mysterious because it operates behind the scenes, handling functions without explicit instructions from the user. A stack is a type of data structure where values can only be added or removed from the “top” of the stack. A call stack is a stack of frame objects, which is the information from a single function call. Each time a function is called, a new frame object is placed onto the top of the call stack.

New frame objects are created each time a call to a function is made, and it is not until a base case is reached, and the function returns, that frame object is removed from the top of the stack. With each frame object removal, the data cascades down, until the initial function call can be resolved. The following diagram is a visual representation of what happens in the stack with the function _pow_recursion() called to return 3 to the power of 3:

A diagram of a recursive function that returns the power of two positive integers

If you want to see a more animated explanation of how the stack works, here is an excellent demonstration by Computerphile:

One last thing that should be mentioned now that the concept of the stack is introduced, is that each time a frame object is added to the stack, more memory is used. In the case of our recursive functions without base cases, it actually doesn’t produce infinite output as it would with with infinite iterative loops. Since stack memory is used with each function call, and the functions call without end, the result is a stack overflow, a terminal error during execution. In the Python examples, the error reached is a maximum recursion depth, or the the maximum call stack size. The Python interpreter limits the program’s execution after 1000 function calls to prevent stack overflows caused by a recursive program without end.

Structure of Recursive Functions

Now that we have an understanding of the components of recursion, I would like to summarize by once going over the flow of recursive functions, and mention one breakdown on how to approach the creation of recursive functions.

A more mathematical definition hints at a way to structure recursive functions usefully:

Recursion in computer science is a method of solving a problem where the solution depends on solutions to smaller instances of the same problem.

~https://en.wikipedia.org/wiki/Recursion_(computer_science)

Here, the fundamental concept of breaking down problems into smaller problems is introduced. In the previous example where the power of two numbers was calculated, the recursive case had the parameters reduced each time, until the parameters met the base condition.

A general flow of the execution of recursive functions can be stated as:

1. Initialize the function with data.
2. Check to see whether the current value(s) being processed match the base case. If so, process and return the value.
3. Redefine the answer in terms of a smaller or simpler sub-problems
4. Run the algorithm on the sub-problem.
5. Combine the results in the formulation of the answer.
6. Return the results.

(Adapted from: https://www.ibm.com/developerworks/library/l-recurs/index.html)

As we determined before, the base case in the condition where the function will return a value. Once this base state is determined, then the task of determining how to structure the recursive case can be defined. It is a matter of trying to define a function call with the parameters modified in such a way that the problem is slightly simpler.

Consider the following Python script that reverses a string with recursion:

def reverse(string):
    if len(string) < 2:
        return(string)
    return reverse(string[1:]) + string[0]print(reverse("moose"))

Output:

esoom

In this example, for the recursive call, we have created smaller sub-problems by slicing the first character from the string, making a smaller string to return. And since we know that with each subsequent call, the string will get shorter, we have determined to set the base case to return the string with it is one (or less) characters. Also knowing how the stack works is critical in surmising that the resulting output will be the string in reverse, since the frame objects will be resolved from the top of the stack, it can be determined that each time the return string will be rebuilt from the last characters sliced from the string first, effectively reversing the string.

Daniel King describes this well in his article on learning to think with recursion:

I did not think about how I could break the problem down all the way to the base case. That is the function’s job, not yours. Instead, I only thought about the problem that is one step simpler than the problem I am really trying to solve, and then I wrote my recursive algorithm to build up from there to solve the real problem.

Concluding Remarks

Even with all the concepts grasped, like any aspect of programming, to effectively use recursion, it takes practice to master. Here is an comprehensive overview with further examples from popular recursive algorithms that can be referenced to further deepen one’s understanding of recursion