a recursive Fibonacci function in Clojure

recursion clojure fibonacci
richc picture richc · Jan 20, 2012 · Viewed 16.4k times · Source

I'm a newcomer to clojure who wanted to see what all the fuss is about. Figuring the best way to get a feel for it is to write some simple code, I thought I'd start with a Fibonacci function.

My first effort was:

(defn fib [x, n]
  (if (< (count x) n) 
    (fib (conj x (+ (last x) (nth x (- (count x) 2)))) n)
    x))

To use this I need to seed x with [0 1] when calling the function. My question is, without wrapping it in a separate function, is it possible to write a single function that only takes the number of elements to return?

Doing some reading around led me to some better ways of achieving the same funcionality:

(defn fib2 [n]
  (loop [ x [0 1]] 
    (if (< (count x) n) 
      (recur (conj x (+ (last x) (nth x (- (count x) 2)))))
      x)))

and

(defn fib3 [n] 
  (take n 
    (map first (iterate (fn [[a b]] [b (+ a b)]) [0 1]))))

Anyway, more for the sake of the exercise than anything else, can anyone help me with a better version of a purely recursive Fibonacci function? Or perhaps share a better/different function?

Answer

vedang picture vedang · Jan 20, 2012

To answer you first question:

(defn fib
  ([n]
     (fib [0 1] n))
  ([x, n]
     (if (< (count x) n) 
       (fib (conj x (+ (last x) (nth x (- (count x) 2)))) n)
       x)))

This type of function definition is called multi-arity function definition. You can learn more about it here: http://clojure.org/functional_programming

As for a better Fib function, I think your fib3 function is quite awesome and shows off a lot of functional programming concepts.

Related questions

Clojure: Simple factorial causes stack overflow

What am I doing wrong? Simple recursion a few thousand calls deep throws a StackOverflowError. If the limit of Clojure recursions is so low, how can I rely on it? (defn fact[x] (if (<= x 1) 1 (* x (fact (- x 1)) ))) …

Read More
What is the maximum recursion depth in Python, and how to increase it?

I have this tail recursive function here: def recursive_function(n, sum): if n < 1: return sum else: return recursive_function(n-1, sum+n) c = 998 print(recursive_function(c, 0)) It works up to n=997, then it just breaks and spits …

Read More
Recursively look for files with a specific extension

I'm trying to find all files with a specific extension in a directory and its subdirectories with my bash (Latest Ubuntu LTS Release). This is what's written in a script file: #!/bin/bash directory="/home/flip/Desktop" suffix="in" browsefolders () …

Read More