Challenge: Write the recursive Fibonacci algorithm in a different language.

Argh, I was going to write a similar one in Elixir! I do like your join with the arrow!

An Emacs Lisp version. Warning!! This will likely freeze your Emacs!!

(defun fib(n)
         (cond
          ((= n 0) 0)
          ((= n 1) 1)
          (t (+ (fib (- n 1)) (fib (- n 2))))))

UPDATE
Just realized it counts as a Common Lisp version too

Lord, we got it, you're the best fibonnaci solver out there. Congratulations on this!

Here's a Python variant for quite large numbers. Alas, due to recursion depth restrictions, any new calculated Fibonacci number should not have a larger sequence position than about 500 more than that of the highest already calculated.

def fib(a, F={}):
    if a in F:
        return F[a]
    if a < 2:
        return 1
    f = fib(a-1)
    F[a-1] = f
    return f + fib(a-2)

for i in range(0,50001,500):
    print("fib(%i) = %i"%(i,fib(i)))

I have haskell here with the best form of recursion: Self-recursion!

fibs = 1:1:zipWith (+) fibs (tail fibs)
fib n = fibs !! n

Here fibs is an infinite List of all fibonacci numbers, the !! function returns the nth element of the list.

#include <iostream>

constexpr long long fibonacci(long long i) {
    if (i <= 2) {
        return 1LL;
    }
    return fibonacci(i - 1) + fibonacci(i - 2);
}

int main() {
    std::cout << "Fibonacci of 27 is " << fibonacci(27) << std::endl;
    return 0;
}

Modern C++ can do it more simply, though - this uses constexpr to tell the compiler that it can calculate these at build time if it wants. Using a constexpr arg (here a literal), it probably will do, but we could also pass in a variable to make it calculate it at runtime.

#include <iostream>

template<long long i> long long fibonacci() {
    return fibonacci<i-1>() + fibonacci<i-2>();
}

template<> long long fibonacci<1>() {
    return 1;
}

template<> long long fibonacci<2>() {
    return 1;
}

int main() {
    std::cout << "Fibonacci of 27 is " << fibonacci<27>() << std::endl;
    return 0;
}

C++ can, of course, do it at build time with a bit of templates.

Here, we're definitely recursing - twice, because it's simpler. At runtime, it's just printing the value out that's been calculated by the compiler during the build.

def fib(arg):
  curr, prev = 1, 1
  n = int(arg)
  if n != arg or n <= 0:
    raise ValueError("Argument must be positive integer")
  if n <= 2:
    return 1
  for count in range(n - 2):
    curr, prev = curr + prev, curr
  return curr

Quick bit of Python. The error handling probably isn't complete, but Python has the useful benefit here that it has native, transparent, Big Number support - you can do fib(10000) if you want (or much higher if you have the memory).

But yeah, I just noticed Douglas wanted a recusrive algorithm, whereas I've done it iteratively without thinking. In general, iterative solutions will execute faster - though this isn't always the case.

As a Ruby fan, I'm sure glad Ruby has such a great ambassador in here.

Funge++:

v   >:1-\2-101O\101O+B
 :1`|
    >$1B
>&:!#v_101O.55+,
     @

I did this some time ago in Rust.

My first approach (the naive one) is very similar to @rapidnerd 's (George Marr's) solution in R and @andreanidouglas ' (Douglas R Andreani's) solution in Python:

fn fib(n: u64) -> u64 {
  match n {
    0 => 0,
    1 => 1,
    _ => fib(n-1) + fib(n-2),
  }
}

I realized that this solution quickly exceeded in execution time for n > 40, so I optimized it using a mathematical theorem:

Given that n and p are integers, and that n = 2p + 1, i. e. n is odd, the n-th fibonacci number is then

fib(n) = fib(p + (p+1)) = fib(p)² + fib(p+1)²

This means, we can break down numbers with odd indices into to numbers with about the half of the index – and do this again and again and again. This dramatically reduces execution time:

fn fib_fast(n: u64) -> u64 {
  match n {
    0 => 0,
    1 => 1,

    // even
    _ if n % 2 == 0 => fib_fast(n-1) + fib_fast(n-2),

    // odd
    _ => {
      let a = (n-1)/2;
      let b = n-a;
      let fib_a = fib_fast(a);
      let fib_b = fib_fast(b);
      return fib_a*fib_a + fib_b*fib_b;
    },
  }
}

Inspired by @avalander 's answer, I also added this even faster algorithm:

fn fib_super_fast(n: u64, i: u64, curr: u64, prev: u64) -> u64 {
  if i >= n {
    return curr;
  }

  return fib_super_fast(n, i + 1, curr + prev, curr);
}

fib_fast and fib_super_fast execute within microseconds even for higher indices. However, indices of 94 and higher cause a crash:

thread 'main' panicked at 'attempt to add with overflow', src/main.rs:42:35

Some performance measurements:

Enter n:
5
fib_super_fast(n) = 5 (0µs)
fib_fast(n)       = 5 (0µs)
fib(n)            = 5 (1µs)

Enter n:
20
fib_super_fast(n) = 6765 (1µs)
fib_fast(n)       = 6765 (10µs)
fib(n)            = 6765 (536µs)

Enter n:
40
fib_super_fast(n) = 102334155 (1µs)
fib_fast(n)       = 102334155 (54µs)
fib(n)            = 102334155 (1908011µs)

Enter n:
45
fib_super_fast(n) = 1134903170 (2µs)
fib_fast(n)       = 1134903170 (15µs)
fib(n)            = 1134903170 (21216762µs)

Enter n:
90
fib_super_fast(n) = 2880067194370816120 (2µs)
fib_fast(n)       = 2880067194370816120 (958µs)

Enter n:
93
fib_super_fast(n) = 12200160415121876738 (3µs)
fib_fast(n)       = 12200160415121876738 (152µs)

Enter n:
94
thread 'main' panicked at 'attempt to add with overflow', src/main.rs:42:35

Common Lisp!

(defun fib (n &optional (curr 0) (next 1)) 
  (if (zerop n) 
      curr 
      (fib (1- n) next (+ curr next))))

(and for the TCO crowd... it's implementation dependent, so YMMV)

@mudasobwa I think pointing out a defect, or even just something that can be improved is fine. However I do think that making your point once is good enough. Also I recommend an approach where you say something like “this works fine when N is small enough, but you can extend the domain of this function to larger input values if you avoid using recursion.” If you can make your point while remaining friendly, why not do so?

I'll continue with it in R

fibR <- function(n) {
    if ((n == 0) | (n == 1)) 
        return(1)
    else
        return(fibR(n-1) + fibR(n-2))
}

fibR(20)