Logo

Programming-Idioms

# 301 Recursive Fibonacci sequence
Compute the Fibonacci sequence of n numbers using recursion.

Note that naive recursion is extremely inefficient for this task.
New implementation

Be concise.

Be useful.

All contributions dictatorially edited by webmasters to match personal tastes.

Please do not paste any copyright violating material.

Please try to avoid dependencies to third-party libraries and frameworks.

Other implementations 
int fibonacci(int n) => n <= 2 ? 1 : fibonacci(n - 2) + fibonacci(n - 1);

  recursive function f (n) result(res)
    integer, value, intent(in) :: n
    integer :: res
    if (n == 0) then
       res = 0
    else if (n <= 2) then
       res = 1
    else
       if (mod(n,2) == 1) then
          res = f((n + 1)/2)**2 + f((n - 1)/2)**2
       else
          res = f(n/2) * (f(n/2-1) + f(n/2 + 1))
       end if
    end if
  end function f
func fibonacci(n int) int {
	if n <= 1 {
		return n
	}
	return fibonacci(n-1) + fibonacci(n-2)
} 
fib :: Int -> Int
fib 0 = 0
fib 1 = 1
fib n = fib n-1 + fib n-2
(defun fibonacci (n &optional (a 0) (b 1) (acc ()))
  (if (zerop n)
      (nreverse acc)
      (fibonacci (1- n) b (+ a b) (cons a acc))))
function fib(n: word): uint64;
begin
  if (n in [0,1]) then
    result := n
  else
    result := fib(n-2) + fib(n-1);
end; 
sub fib {
    my ($n) = @_;
    die if $n < 0;
    return 1 if $n < 2;
    return fib($n-1) + fib($n-2);
}

def fib(n):
    if n < 0:
        raise ValueError
    if n < 2:
        return n
    return fib(n - 2) + fib(n - 1)
        
def fib(n) = n < 2 ? n : fib(n-1) + fib(n-2)

fn fib(n: i32) -> i32{
    if n < 2 {
        1
    }else{
        fib(n - 2) + fib(n - 1)
    }
}

Preview