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.
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:
b;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:
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!