# Idiom #301 Recursive Fibonacci sequence

Compute the Fibonacci sequence of n numbers using recursion.

Note that naive recursion is extremely inefficient for this task.

``````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)
}
}``````

Sikon