Logo

Programming-Idioms

  • JS
  • Fortran

Idiom #301 Recursive Fibonacci sequence

Compute the Fibonacci sequence of n numbers using recursion.

Note that naive recursion is extremely inefficient for this task.

  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

The function has to be marked recursive. Because it calls itself, it needs a result clause for the name of the result.

The algorithm (a bit more efficient than straight recursion) is due to https://oeis.org/A331124 .
int fibonacci(int n) => n <= 2 ? 1 : fibonacci(n - 2) + fibonacci(n - 1);
New implementation...
< > ⌨
Sikon 
  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
int fibonacci(int n) => n <= 2 ? 1 : fibonacci(n - 2) + fibonacci(n - 1);

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