## DEV Community 👩‍💻👨‍💻

Nic

Posted on • Originally published at coderscat.com on

# 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. 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.

Timeless DEV post...

## Git Concepts I Wish I Knew Years Ago

The most used technology by developers is not Javascript.

It's not Python or HTML.

It hardly even gets mentioned in interviews or listed as a pre-requisite for jobs.

I'm talking about Git and version control of course. 