DEV Community

Nic
Nic

Posted on • Originally published at coderscat.com on

Understanding Recursion and Continuation with Python

#python #recursion #programming

photo-1554900773-4dd76725f876.jpeg

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))
Enter fullscreen mode Exit fullscreen mode

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))
Enter fullscreen mode Exit fullscreen mode

The output will be:

2020_05_08_understanding-tail-recursive-and-csp-with-python.org_20200509_125520.png

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))
Enter fullscreen mode Exit fullscreen mode

The output is like this:

2020_05_08_understanding-tail-recursive-and-csp-with-python.org_20200509_174510.png

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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))
Enter fullscreen mode Exit fullscreen mode

The output is:

<function <lambda> at 0x101d52758>
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

Then run it with:

print(trampoline(fib_cps, 5, end_cont))
Enter fullscreen mode Exit fullscreen mode

2020_05_08_understanding-tail-recursive-and-csp-with-python.org_20200509_190057.png

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.

Top comments (1)

Collapse
 
mike239x profile image
Mike Lezhnin •

I think I understood it, but the example with continuations is still quite mind-blowing.
I probably would have rewritten it like so:

import traceback

def fib_cnt ( state ) :
    print(len(traceback.extract_stack()) * '*' + ": " + str(state))
    if state['finished'] :
        return state
    if len(state['values']) == 0 :
        state['finished'] = True
        return state
    n = state['values'].pop()
    if n < 2:
        state['acc'] += 1
        return state
    state['values'].append(n-1)
    state['values'].append(n-2)
    return state

def fib (n) :
    state = dict ( values = [n], acc = 0, finished = False )
    while not state['finished'] :
        state = fib_cnt(state)
    return state['acc']

print(fib(5))

This way most of the state is quite transparent and not hidden behind lambdas.

Read next

cereal84 profile image

Hacktoberfest from a maintainer's point of view

Alessandro Pischedda -

testifytech profile image

How to Generate Extent Reports in Selenium

Steve Wortham -

theekshana profile image

The 5 Most Underrated Python Libraries You Should Start Using Right Now

Theekshana Chamodhya -

mrcaption49 profile image

CRUD FUNCTIONALITY in Django

Pranav Bakare -