Recursion and Loops
28 Jun 2010Write a program to find the nth number in the fibonacci series
Imperative Programmer (Earlier)
public void int fib(int n) {
int a = -1,b = 1;
for(int i = 0 ; i < n ; i++){
c = a + b;
a = b;
b = c;
}
return b;
}
can you write this in any other way?
hmm.. blink...
Functional Programmer (Now)
(define (fib x)
(if (or (= x 0) (= x 1))
x
(+ (fib (- x 2)) (fib (- x 1)))))
can you write this in any other way?
hmm.. well.. i can write it using tail recursion
(define (fib x)
(define (fib-iter a b count)
(if (= 0 count)
a
(fib-iter b (+ a b) (- count 1))))
(fib-iter 0 1 x))