Fibonacci sequence

[Craig Marshall]

Hi,

I'm trying to learn lisp and Clojure and so I'm trying some excercises
suggested here on the group a while ago.

I'm not doing too well, I had to cheat on excercise one (make a series
of integers) by looking at the source code to the range function, and
I'm now having to ask for help with excercise two!

I know I could just find a different implementation online, but I
would prefer to understand why my method doesn't work. If anyone can
point to my mistake(s), I'd be very grateful..

(defn fib-helper [a b]
(fib-helper b (+ a b)))

(defn fib (fib-helper 0 1)) ; This doesn't work either: (defn fib (fib-
helper '(0 1)))

(println (take 5 fib))

Thanks in advance,
Craig

[David Nolen]

(defn fib-helper [a b]
 (fib-helper b (+ a b)))

(defn fib (fib-helper 0 1)) ; This doesn't work either: (defn fib (fib-
helper '(0 1)))

You're missing your argument list for fib.

 

(println (take 5 fib))

take creates a lazy list from a collection:

(take n collection)

Your fib does not produce a collection.

David

[Michael Wood]

On Sun, Dec 28, 2008 at 6:01 PM, Craig Marshall <cra...@gmail.com> wrote:
>
> Hi,
>
> I'm trying to learn lisp and Clojure and so I'm trying some excercises
> suggested here on the group a while ago.
>
> I'm not doing too well, I had to cheat on excercise one (make a series
> of integers) by looking at the source code to the range function, and
> I'm now having to ask for help with excercise two!
>
> I know I could just find a different implementation online, but I
> would prefer to understand why my method doesn't work. If anyone can
> point to my mistake(s), I'd be very grateful..
>
> (defn fib-helper [a b]
> (fib-helper b (+ a b)))

This defines an infinitely recursive function. It never actually
returns anything, so it quickly exhausts the stack. Were you trying
for a lazy infinite sequence of fibonacci numbers?

> (defn fib (fib-helper 0 1)) ; This doesn't work either: (defn fib (fib-
> helper '(0 1)))
>
> (println (take 5 fib))

It looks like you want to use (def fib ...) instead of (defn fib ...),
but because of the infinitely recursive fib-helper this will not get
you much further :)

For exercise two, perhaps you should try for the traditional recursive
definition of fib?

i.e. if I want to calculate the nth fibonacci number, I have to first
calculate the (n-1)th and (n-2)th fibonacci numbers and then add them
together and return the result. At some point this has to terminate,
so you need to make sure that there is a way out of the recursion.
(You're probably already familiar with recursion, in which case, sorry
for stating the obvious :)

clojure.contrib.lazy-seqs has a lazy infinite sequence implementation.

--
Michael Wood <esio...@gmail.com>

[Craig Marshall]

Hi David,

>> (defn fib (fib-helper 0 1)) ; This doesn't work either: (defn fib (fib-
>> helper '(0 1)))

> You're missing your argument list for fib.

I assumed you meant the empty square brackets [] just after the work
fib? I didn't realise these were necessary even when there were no
function arguments. Thanks.

>> (println (take 5 fib))
>
> take creates a lazy list from a collection:
> (take n collection)
> Your fib does not produce a collection.

I see. I think I had my algorithm in a twist, I tried to make that
two-function algorithm work in python (and then translate), but failed
at the first hurdle. I've since tried to go for the single function
recursive algorithm.

Thanks,
Craig

[Craig Marshall]

>> (defn fib-helper [a b]
>> (fib-helper b (+ a b)))

> This defines an infinitely recursive function. It never actually
> returns anything, so it quickly exhausts the stack. Were you trying
> for a lazy infinite sequence of fibonacci numbers?

Yes - exactly, I couldn't figure it out, even after trying the same
"algorithm" in python.. I don't like giving up on it though! I would
like to see something like this version "working" somehow. I will
probably come back to it when I have learned more.

>> (defn fib (fib-helper 0 1)) ; This doesn't work either: (defn fib (fib-
>> helper '(0 1)))

> It looks like you want to use (def fib ...) instead of (defn fib ...),

> but because of the infinitely recursive fib-helper this will not get
> you much further :)

Yes - I fixed this (or put in the empty arg list - I don't remember),
and got a heap overflow error or similar. So you were right. If I'd
seen that message before I'd have figured out there was an infinite
recursion somewhere.

> For exercise two, perhaps you should try for the traditional recursive
> definition of fib?

I finally got it working without looking at someone elses code.

(defn fib [n]
(if (<= n 1) ; if 0 or 1
n ; return same, else...
(let [n1 (fib (- n 1)) ; calculate n-1 fib
n2 (fib (- n 2))] ; and n-2
(+ n1 n2)))) ; return sum of n-1 and n-2

(println (fib 9))

I had to start with the python equivalent:

def fib(n):
if n <= 1: return n
n_1 = fib(n-1)
n_2 = fib(n-2)
return n_1 + n_2

print fib(9) # Should be 34

and translate to clojure, which hopefully is something I won't have to
do forever as I understand clojure more.

Thanks,
Craig

[Paul Barry]

Craig,

Something you should be aware of is that this implementation of
Fibonacci is very inefficient. For more info as to why, you can read:

http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2.2

The short story is doing it this way performs a lot of wasted
calculations as n gets larger:

user=> (time (fib 40))
"Elapsed time: 54768.247 msecs"
102334155

If you use this implementation, it uses an iterative process, and is
therefore much faster:

user=> (defn fib [n]
(loop [a 1 b 0 count n]
(if (zero? count)
b
(recur (+ a b) a (dec count)))))
#'user/fib
user=> (fib 9)
34
user=> (time (fib 40))
"Elapsed time: 0.06 msecs"
102334155