Understanding Recursion and Continuation with Python

Figure 1: Photo by Amelie & Niklas Ohlrogge on Unsplash

In the article How To Learn All Programming Languages, I explained learning programming language concepts is an effective way to master all programming language.

Recursion , continuation , and continuation-passing style are essential ideas for functional programming languages. Have an understanding of them will help much in knowing how programming languages work; even we don’t use them in daily programming tasks.

In this post, let’s learn these concepts of programming languages with some short Python programs.

Recursion

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

Most modern programming language support recursion by allowing a function to call itself from within its own code. Recursion is the default programming paradigm in many functional programming languages, such as Haskell, OCaml.

Many daily programming tasks or algorithms could be implemented in recursion in a simpler manner. Suppose you want to list all the files and sub-directories of a directory recursively, recursion will be a natural choice for implementation.

Let’s have a look at this simple recursive Python program:

def fib_rec(n):
    if n < 2:
        return 1
    else:
        return fib_rec(n - 1) + fib_rec(n - 2)

print(fib_rec(5))

It is a naive implementation for computing Fibonacci numbers. A key point of recursion is there must be an exit point, the third line of return 1 is the exit point for this program.

But what is the drawback of recursion?

Let’s add more debug information for this program, print the call depth in the beginning of function:

import traceback
def fib_rec(n):
    print(len(traceback.extract_stack()) * '*' + ": " + str(n))
    if n < 2:
        return 1
    else:
        return fib_rec(n - 1) + fib_rec(n - 2)

print(fib_rec(5))

The output will be:

The * implies the call depths of the current function call. As we can see from the output, there are 2 points that need to notice:

1. There are duplicated computations during the whole progress. fib_rec(3), fib_rec(2), fib_rec(1) are called multiple times.
2. The call stacks will grow quickly as the input number increase. Stack overflow exception will be thrown out if we want to compute fib_rec(1000).

How could we fix these general issues of recursion?

Tail Recursion

Tail recursion is a special form of recursion, in which the final action of a procedure calls itself again. In above program, the last action is return 1 or return fib_rec(n-1) + fib_rec(n-2), this is not a tail recursion.

Let’s try to convert above program to tail recursion:

def fib_tail(n, acc1=1, acc2=1):
    print(len(traceback.extract_stack()) * '*' + ": " + str(n))
    if n < 2:
        return acc1
    else:
        return fib_tail(n - 1, acc1 + acc2, acc1)

print(fib_tail(5))

The output is like this:

From the result, we could find out we removed some duplicated computations, we solved the issue #1 of the above program.

Tail Call Optimization (TCO)

There is a technical called tail call optimization which could solve the issue #2, and it’s implemented in many programming language’s compilers. But not implemented in Python. Guido explains why he doesn’t want tail call optimization in this post.

Anyway, let’s have an understanding of how tail call optimization works. We know that any call of sub-function will create a new stack frame during the execution. If we treat function call as a black box, we could reuse the same stack frame when the tail function call happens.

To do this, a compiler with TCO will try to eliminate the last tail call with a jump operation and fix the issue of stack overflow. Suppose if Python have a goto operation, we could replace the last call of fib_tail with goto and update the related parameters.

# NOTE!!! This is pseudo-code

def fib_tail(n, acc1=1, acc2=1):
    START:
    if n < 2:
        return acc1
    else:
        #return fib_tail(n - 1, acc1 + acc2, acc1)
        n = n - 1
        tmp = acc1
        acc1 = acc1 + acc2
        acc2 = tmp
        goto START

From the result, the compiler actually could convert a recursive function into an iterative version. All iterative functions can be converted to recursion because iteration is just a special case of recursion (tail recursion).

This is the reason why many FP don’t perform poorly even we write code in recursive style. Compilers do their job!

Continuation-passing style

And even more, functional programming languages adopt the continuation-passing style (CPS), in which control is passed explicitly in the form of a continuation.

A continuation is an abstract representation of the control state of a program.

Sounds obscure?

Let’s say continuation is a data structure that represents the computational process at a given a point in the process’s execution, we could save an execution state and continue the computational process latter.

Seems like lambda function in Python could be used for this, since we could pass a lambda function as parameters and call them later.

Let’s define a simplest continuation, this continuation will return the original value with any parameter:

end_cont = lambda value: value

Then we try to convert the above fib_tail function into a CPS. We add a extra parameter called cont:

def fib_cps(n, cont):
    print(len(traceback.extract_stack()) * '*' + ": " + str(n))
    if n < 2:
        return cont(1)
    else:
        return lambda: fib_cps(
                         n - 1,
                         lambda value:
                           lambda: fib_cps(
                                     n - 2,
                                     lambda value2:
                                       lambda: cont(value + value2)))
print(fib_cps(5, end_cont))

The output is:

<function <lambda> at 0x101d52758>

Emm, we only got a lambda function as a result. Remember we could continue to execute a continuation, so we continue to run this lambda function, the returned value is still a continuation …

v = fib_cps(5, end_cont)
print(v)

print(v)
v = v()
print(v)

v = v()
print(v)

v = v()
print(v)

....

**: 5
<function <lambda> at 0x10d493758>
***: 4
<function <lambda> at 0x10d493848>
***: 3
<function <lambda> at 0x10d4938c0>
***: 2
<function <lambda> at 0x10d493938>
***: 1

Let’s wrap a function to call v repatedly until we got a real value:

def trampoline(f, *args):
    v = f(*args)
    while callable(v):
        v = v()
    return v

Then run it with:

print(trampoline(fib_cps, 5, end_cont))

Woo! The stack depth always keeps the same during the execution procedure. Some compilers of functional programming languages will do CPS-transform automatically.

Continuations are also useful for implementing other control mechanisms in programming languages such as exceptions, generators, coroutines, and so on.

Summary up

We have a little but real experience of tail recursion, tail call optimization, and continuation. I know we won’t write code with this style in daily programming. But these concepts helps me to understand programming languages deeper, and they are fun!

I hope you enjoy it.

The post Understanding Recursion and Continuation with Python appeared first on Coder's Cat.