Looking for a specific post? Checkout the Blog Index.

Feb 14th, 2019 - written by Kimserey with .

Recursion refers to the property of a function to be defined in term of itself. The Fibonacci sequence is a great example of a recursive problem where a Fibonacci number is calculated from a combination of precedent Fibonacci numbers. Recursion can be implemented in many forms, it is even possible to implement recursion without explicit *self calling*.
Today we will look at different implementations of Fibonacci and discover their properties.

- Fibonacci
- Iterative Approach
- Recursive Approach
- Tail Recursion
- Continuation Passing Style
- Y Combinator

Let’s start by first defining what a Fibonacci sequence is.

1
2
3
4

f(n) = f(n-1) + f(n-2)
f(0) = 0
f(1) = 1

Each Fibonacci number is calculated by taking the *previous* Fibonacci number and adding it to the *previous-previous* Fibonacci number. With initial values for `0`

and `1`

being `f(0)=0`

and `f(1)=1`

.
With this definition, we can compute the following sequence:

1
2
3
4
5
6
7
8
9
10
11

f(0) = 0
f(1) = 1
f(2) = 1 (0+1)
f(3) = 2 (1+1)
f(4) = 3 (1+2)
...
f(10) = 55
f(11) = 89
...
f(20) = 6765
f(21) = 10946

Before looking into recursion, we’ll look first at how we can represent Fibonacci using a `for`

loop and mutable variables, also know as an **Iterative approach**.

A `for`

loop in Racket is represented with `(for (for-clause ...) body-or-break ... body)`

. The `for-clause`

can be given as a *sequence* `[id seq-expr]`

or as a number. If a number is provided, it is interpreted as `(in-range n)`

. Armed with our knowledge of `for`

loop, we can represent our first iterative version of Fibonacci `fibonacci-0`

:

1
2
3
4
5
6
7
8
9
10
11

(define fibonacci-0
(λ (n)
(cond
[(zero? n) 0]
[else
(define-values (a b tmp) (values 0 1 0))
(for ([i (- n 1)])
(set! tmp a)
(set! a b)
(set! b (+ tmp b)))
b])))

Given a number `n`

, we immediately return `0`

for `n=0`

. Else we define mutable variables `a`

and `b`

with initial values respectively set to `0`

for `f(0)`

and `1`

for `f(1)`

. Next we enter a `for`

loop going from `0 to n-1`

. At each beginning of loop’s iteration, `a`

represents `f(iteration-2)`

and `b`

represents `f(iteration-1)`

. To compute `f(iteration)`

, we swap `a`

with `b`

and set `b`

to `b + tmp`

where `tmp`

is the previous value of `a`

(prior being set to `b`

). At the end of the loop, we return `b`

which contains `f(n)`

.

If we run through a compilation of `n=0`

, `n=1`

and `n=2`

, we get the following:

`n=0`

,`0`

is directly returned from the first condition;`n=1`

,`a`

and`b`

is set to`0`

and`1`

, the loop is never entered as`n-1 = 1-1 = 0`

and`b=1`

is returned;`n=2`

, the loop is iterated one time where`b`

is set to`tmp+b = 1+1 = 2`

and`b=2`

is returned.

In the same way, we can see how the iteration will calculate the Fibonacci numbers by replacing in turn `a`

and `b`

.

1
2

>(fibonacci-0 5)
5

Recursion occurs when a procedure is defined in term of itself. Fibonacci is inherently recursive, `f(n)`

is the result of the sum between the previous Fiboonacci number `f(n-1)`

and the *previous-prevous* number `f(n-2)`

. The procedure computing Fibonacci number can be described identically to its equation:

1
2
3
4
5
6

(define fibonacci-1
(λ (n)
(cond
[(zero? n) 0]
[(= n 1) 1]
[else (+ (fibonacci-1 (- n 1)) (fibonacci-1 (- n 2)))])))

Given a number `n`

, we immediately return `0`

for `n=0`

and `1`

for `n=1`

. Else we add `f(n-1)`

and `f(n-2)`

by *recursively* calling the procedure `fibonacci-1`

.

If we run through a compilation of `n=0`

, `n=1`

and `n=4`

, we get the following:

`n=0`

,`0`

is directly returned from the first condition;`n=1`

,`1`

is directly returned from the second condition;`n=4`

, we get`3`

as explained below.

For `n=4`

, by substitution we would get the following:

1
2
3
4
5
6
7
8
9

> (+ (fib (- n 1)) (fib (- n 2)))
>> (+ (fib (- 4 1)) (fib (- 4 2)))
>>> (+ (fib 3) (fib 2))
>>>> (+ (+ (fib 2) (fib 1)) (+ (fib 1) (fib 0)))
>>>>> (+ (+ (+ (fib 1) (fib 0)) 1) (+ 1 0))
>>>> (+ (+ (+ 1 0) 1) 1)
>>> (+ (+ 1 1) 1)
>> (+ 2 1)
> 3

The result of each recursive call results in another recursive call until an *exit* condition is met stopping the recursion.
The substitution of the recursive approach highlights a pymarid shape. In Racket, the shape of a function can be observed using `trace`

from `(require racket/trace)`

. `trace`

traces the last call of an expression, also known as the **Tail call**. In this example, the tail call is the arithmetic `+`

procedure occuring once all `fibonacci-1`

calls have been subtituted with primitive values.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

(trace fibonacci-1)
>(fibonacci-1 4)
> (fibonacci-1 3)
> >(fibonacci-1 2)
> > (fibonacci-1 1)
< < 1
> > (fibonacci-1 0)
< < 0
< <1
> >(fibonacci-1 1)
< <1
< 2
> (fibonacci-1 2)
> >(fibonacci-1 1)
< <1
> >(fibonacci-1 0)
< <0
< 1
<3
3

Recursion can also be achieved using an **aggregator**. An aggregator is a value containing the result of each recursive call and passed as input to the next recursive call until a predicate is reached in which instance the aggregator is returned as final result. This method is sometime called **aggregator passing style (aps)**.

For example with Fibonacci, we need to aggregate `f(n-1)`

and `f(n-2)`

as they will be the *running* values needed for the next computation.

1
2
3
4
5
6

(define fibonacci-aps
(λ (a b n)
(cond
[(zero? n) 0]
[(= n 1) b]
[else (fibonacci-aps b (+ a b) (- n 1))])))

`fibonacci-aps`

takes `a`

and `b`

as extra parameters to keep track of `f(n-1)`

and `f(n-2)`

. Instead of using `n`

as the Fibonacci number, we use `n`

as a iteration counter and compute `f(n)`

by adding `a + b`

and `f(n-1)`

by passing `b`

.

To respect the same signature as `fibonacci-1`

, we partially apply `fibonacci-aps`

with initial parameters `0`

and `1`

.

1

(define fibonacci-2 (λ (n) (fibonacci-aps 0 1 n)))

If we run through a compilation of `n=0`

, `n=1`

and `n=4`

, we get the following:

`n=0`

,`0`

is directly returned from the first condition;`n=1`

,`1`

is directly returned from the second condition;`n=4`

, we get`3`

as explained below.

1
2
3
4
5
6

> n a b (fibonacci-aps b a+b n-1)
> n=4 a=0 b=1 (fibonacci-aps 1 1 3 )
> n=3 a=1 b=1 (fibonacci-aps 1 2 2 )
> n=2 a=1 b=2 (fibonacci-aps 2 3 1 )
> n=1 a=2 b=3 (b)
> 3

At each tail call, the next recursive is a call with aggregators passed. In comparison to the previous recursive definition `fibonacci-1`

where each tail call needed expansion of parameters involving recursive calls, in aggregator passing style, the parameters are all primitive values and the **tail call is a call to itself**. This property is known as **Tail recursion**.

An interesting aspect of the difference between `fibonacci-1`

and `fibonacci-2`

is their shapes. If we trace the `fibonacci-aps`

, we get a linear shape compared to `fibonacci-1`

which was a pyramid shape.

1
2
3
4
5
6
7

> (fibonacci-2 4)
>(fibonacci-aps 0 1 4)
>(fibonacci-aps 1 1 3)
>(fibonacci-aps 1 2 2)
>(fibonacci-aps 2 3 1)
<3
3

Some compilers take advantage of this property to represent recursive calls in constant space by replacing each stack space with the latest as each iteration of `fibonacci-aps`

does not require knowledge of prior iterations. This implementation is known as **Tail call optimization** or also **Tail call eliminitation**.

Another way of implementing recursion is through continuations. A continuation captures the *rest* of a computation while making it available as a procedure.

Taking our recursive approach of Fibonacci, we had the following:

1
2
3
4
5
6

(define fibonacci-cps
(λ (n)
(cond
[(zero? n) 0]
[(= n 1) 1]
[else (+ (fibonacci-cps (- n 1)) (fibonacci-cps (- n 2)))])))

Continuation passing style revolves around the concept of passing continuation as argument. Following this, we add `k`

the continuation as argument to our procedure:

1
2
3
4
5
6
7
8

(define id (λ (x) x))
(define fibonacci-cps
(λ (n k)
(cond
[(zero? n) (k 0)]
[(= n 1) (k 1)]
[else (k (+ (fibonacci-cps (- n 1) id) (fibonacci-cps (- n 2) id)))])))

Each condition is then represented as its continuation:

`0`

becomes continuation of`0`

;`1`

becomes continuation of`1`

;`(+ (fibonacci-1 (- n 1)) (fibonacci-1 (- n 2)))`

becomes the continuation of itself, and because the recursive call to`fibonacci-1`

requires a continuation`k`

, we provide the identity function`(λ (x) x)`

.

So far we provided the identity function `(λ (x) x)`

as a continuation of `fibonacci-1 (- n 1)`

and `fibonacci-1 (- n 2)`

in order for the procedure to be compilable but it was sort of a lie. Identity is surely not the continuation of the two operations.

If we rearrange the operations in separate bindings we would get the following:

1
2
3
4
5
6
7
8
9

(define fibonacci-cps
(λ (n k)
(cond
[(zero? n) (k 0)]
[(= n 1) (k 1)]
[else
(define a (fibonacci-cps (- n 1) (λ (x) x)))
(define b (fibonacci-cps (- n 2) (λ (x) x)))
(k (+ a b))])))

We have moved the `fibonacci-1`

calls to their own variables definitions. This reorganization highlights three statements which makes their respective continuations clearer.

For the first `(define a (fibonacci-1 (- n 1) (λ (x) x)))`

, the continuation has two steps:

- to define
`b`

; - to call
`k`

with`x + b`

.

1
2
3
4
5
6
7
8
9
10
11

(define fibonacci-cps
(λ (n k)
(cond
[(zero? n) (k 0)]
[(= n 1) (k 1)]
[else
(fibonacci-cps
(- n 1)
(λ (a)
(define b (fibonacci-cps (- n 2) (λ (x) x)))
(k (+ a b))))])))

And similarly for the next definition, we can replace the identity function with the *real* continuation:

- call
`k`

with`a + b`

.

1
2
3
4
5
6
7
8
9
10
11

(define fibonacci-cps
(λ (n k)
(cond
[(zero? n) (k 0)]
[(= n 1) (k 1)]
[else
(fibonacci-cps
(- n 1)
(λ (a) (fibonacci-cps
(- n 2)
(λ (b) (k (+ a b))))))])))

Lastly we can define `fibonacci-3`

, a procedure respecting the signature of our initial Fibonacci procedure.

1

(define fibonacci-3 (λ (n) (fibonacci-cps n (λ (x) x))))

If we run through a compilation of `n=0`

, `n=1`

and `n=4`

, at each step we are building a procedure.

`n=0`

, we get`0`

as the first iteration of`fibonacci-cps`

evaluates the first condition which in turn evaluates`k`

as the identity function with`0`

;

1
2
3
4

(fibonacci-3 0)
> (fibonacci-cps 0 (λ (x) x)
> (λ (0) 0)
> 0

`n=1`

, we get`1`

for the same reason as`n=0`

;`n=4`

, we get`3`

as demonstrated:

1
2
3
4
5

(fibonacci-3 4)
> (fibonacci-cps 4 (λ (x) x)
> (fibonacci-cps 3 (λ (a) (fibonacci-cps 2 (λ (b) (+ a b)))))
> (fibonacci-cps 2 (λ (c) (fibonacci-cps 1 (λ (d) ((λ (a) (fibonacci-cps 2 (λ (b) (+ a b)))) (+ c d))))))
> (fibonacci-cps 1 ###)

From then onward the first condition is executed `(k 1)`

which by substitution results in:

1
2
3
4
5
6
7
8
9
10

> ((λ (c) (fibonacci-cps 1 (λ (d) ((λ (a) (fibonacci-cps 2 (λ (b) (+ a b)))) (+ c d))))) 1)
> ((λ (d) ((λ (a) (fibonacci-cps 2 (λ (b) (+ a b)))) (+ 1 d))) 1)
> ((λ (a) (fibonacci-cps 1 (λ (c) (fibonacci-cps 0 (λ (d) ((λ (b) (+ a b)) (+ c d))))))) 2)
> (fibonacci-cps 1 (λ (c) (fibonacci-cps 0 (λ (d) ((λ (b) (+ 2 b)) (+ c d))))))
> ((λ (c) (fibonacci-cps 0 (λ (d) ((λ (b) (+ 2 b)) (+ c d))))) 1)
> (fibonacci-cps 0 (λ (d) ((λ (b) (+ 2 b)) (+ 1 d))))
> ((λ (d) ((λ (b) (+ 2 b)) (+ 1 d))) 0)
> ((λ (b) (+ 2 b)) 1)
> (+ 2 1)
> 3

By applying continuation passing style, we ended up with a tail recursive procedure where at each iteration of `fibonacci-cps`

, each parameters are primitive values: a number and a procedure.

If we trace `fibonacci-cps`

, we can see that we have a linear shape similarly to the aggregator version except that it contains extra calls used during the *unwrapping* of the continuations.

1
2
3
4
5
6
7
8
9
10
11
12

> (fibonacci-3 4)
>(fibonacci-cps 4 #<procedure:...st/fibonacci.rkt:49:44>)
>(fibonacci-cps 3 #<procedure:...st/fibonacci.rkt:46:8>)
>(fibonacci-cps 2 #<procedure:...st/fibonacci.rkt:46:8>)
>(fibonacci-cps 1 #<procedure:...st/fibonacci.rkt:46:8>)
>(fibonacci-cps 0 #<procedure:...st/fibonacci.rkt:47:32>)
>(fibonacci-cps 1 #<procedure:...st/fibonacci.rkt:47:32>)
>(fibonacci-cps 2 #<procedure:...st/fibonacci.rkt:47:32>)
>(fibonacci-cps 1 #<procedure:...st/fibonacci.rkt:46:8>)
>(fibonacci-cps 0 #<procedure:...st/fibonacci.rkt:47:32>)
<3
3

*Continuations are discussed in more details in our previous post on Implementing Exceptions With Continuations.*

Lastly we can introduce recursion without the procedure calling itself. This method can be achieve using the **Y Combinator** also known as **Fixed-point Combinator**.
The fixed-point (shortened fixpoint) of a function is defined as `x=f(x)`

. It is said that `x`

is the fixpoint of `f`

.

The `Y`

combinator is a procedure taking a function as parameter and returning its fixpoint as result. `f=(Y F)`

where `f`

is the fixpoint of `F`

such as `f=F(f)`

. Here is the definition of `Y`

:

1
2
3
4

(define Y
(λ (f)
((λ (x) (x x))
(λ (x) (f (λ (y) ((x x) y)))))))

`f=(Y F)`

means that if we define `F`

, a function having as fixpoint a Fibonacci function, we can use `Y`

to find the Fibonacci function itself.

We start first from our initial Fibonacci and instead of the recursion, we call `f`

, a function representing a Fibonacci function taken as parameter.

1
2
3
4
5
6
7

(define F-fibonacci
(λ (f)
(λ (n)
(cond
[(zero? n) 0]
[(= n 1) 1]
[else (+ (f (- n 1)) (f (- n 2)))]))))

Next we can use `F-fibonacci`

to create a Fibonacci function with `(Y F-fibonacci)`

:

1

(define fibonacci-4 (Y F-fibonacci))

We now have a working Fibonacci procedure without recursion.

1
2

> (fibonacci-4 4)
3

And that concludes today’s post.

Today we saw different ways of implementing a Fibonacci sequence. We started by looking at an iterative way with loops, then we moved to a recursive approach yielding a pyramid shape, then we moved to a tail recursive approach using aggregators, and we looked at a way to produce tail recursion out of a recursive approach by using continuation passing style. Finally, we completed the post by looking at how the Y combinator could be used to bring recursion to a function without it calling itself. I hope you liked this post and I’ll see you on the next one!