Fibonacci Series - LISP(Scheme)
Now in coding for different problems , you might have certainly found the problem to find nth number in a fibonacci series... First of all what is a fibonacci series ?
Well fibonacci series is a series starts with 0 and 1 then further series is evaluated as sum of two previous numbers i.e 0, 1, 1, 2, 3, 5, 8, 13, and so on... One can find good detail on fibonacci series at
Now let us see how we might implement the above problem in lisp...
We want to be able to find nth number , so suppose we want to find 4th number in the series, how will we go about it...
first of all we know that we need to find fibonacci at 4th and for finding Fibonacci number at 4th place we need to add Fibonacci number at 3rd and Fibonacci number at 2nd place, similarly for 3rd place fibonacci number we need to know The Fibonacci number at 2nd and 1st place and similarly for 2nd we need to know The Fibonacci number at 0th and 1st place which we know and so we can see a series being formed following the pattern fib(n) = fib(n-1) + fib(n-2) which looks like:
0 , 1 , 1 , 2 , 3 , 5 , 8 , 13 , 21 , 34 ...
0 , 1 , 1 , 2 , 3 , 5 , 8 , 13 , 21 , 34 ...
So first of all we need to create a procedure taking n, and if we want value of fib 0 or fib 1, we should be able to return it, otherwise we need to calculate (fib n-1) + (fib n-2).
(define (fib n)(cond((= n 0) 0)
((= n 1) 1)
(else(+ (fib (- n 1)) (fib (- n 2))))))
In the above code we simply start by stating the values of n = 0 and n = 1, other than those values we simply ask it to recursively compute two thing's
1. fib(- n 1)
2. fib(- n 2)
and add those up.
The above code will look like :
>(define (fib n)(cond((= n 0) 0)
((= n 1) 1)
(else(+ (fib (- n 1)) (fib (- n 2))))))
in the interpreter.
Lets run the procedure we just created:
>(fib 5)
5
We can write the same program using an iterative approach which helps in a better memory management.
For Iterative approach we simply don't want to store much so we start from what we know and calculate what we don't know rather than keeping track of what we need to calculate...
(define fib-iter a b n)(cond ((= n 1) b)
(else(fib-iter b (+ a b ) (- n 1)))))
a b are initially 0 & 1 respectively and n is the nth fibonacci term we wish to find.
(define (fib n)(cond((= n 0) 0)
((= n 1) 1)
(else(+ (fib (- n 1)) (fib (- n 2))))))
In the above code we simply start by stating the values of n = 0 and n = 1, other than those values we simply ask it to recursively compute two thing's
1. fib(- n 1)
2. fib(- n 2)
and add those up.
The above code will look like :
>(define (fib n)(cond((= n 0) 0)
((= n 1) 1)
(else(+ (fib (- n 1)) (fib (- n 2))))))
in the interpreter.
Lets run the procedure we just created:
>(fib 5)
5
We can write the same program using an iterative approach which helps in a better memory management.
For Iterative approach we simply don't want to store much so we start from what we know and calculate what we don't know rather than keeping track of what we need to calculate...
(define fib-iter a b n)(cond ((= n 1) b)
(else(fib-iter b (+ a b ) (- n 1)))))
a b are initially 0 & 1 respectively and n is the nth fibonacci term we wish to find.
Written By,
Sarvesh Bhatnagar
No comments:
Post a Comment