피보나치 수 프로그램

피보나치 수 프로그램은 피보나치 수를 프로그래밍 언어로 만든 것으로, 일반적으로 재귀적인 방법을 사용한다.

피보나치 수를 정의에 따라 재귀적으로 구하면 일반적으로 거듭제곱의 시간 복잡도가 소요된다. 하지만 한번 구한 값을 저장해서 여러 번 중복해서 계산하지 않는 메모이제이션을 사용하면 O(n)의 복잡도가 소요된다. 또한 수식을 통해 O(log n)의 복잡도로 값을 구할 수도 있다.

아래는 다양한 프로그래밍 언어로 구현된 피보나치 수 프로그램의 예이다.

스킴

Binary recursion, snippet

 (define fibo
  (lambda (x)
    (if (< x 2)
      x
      (+ (fibo (- x 1)) (fibo (- x 2))))))

Θ(F(n)) 시간이 소요된다.

Tail-end recursive, snippet

 (define (fibo x) 
   (define (fibo-iter x a b)
      (if (= x 0) 
             a 
            (fibo-iter (- x 1) b (+ a b))))
   (fibo-iter x 0 1))

Θ(n) 시간에 실행된다.

모두 표시한 코드 조각

 (define (fibo-run a b) 
   (display a)
   (newline)
   (fibo-run b (+ a b)))
 
 (define fibo-run-all (fibo-run 0 1)))

커먼 리스프

루카스 식을 통한 피보나치 계산

(defun fib (n)
  (cond
   ((= n 0) 0)
   ((or (= n 1) (= n 2)) 1)
   ((= 0 (mod n 2)) (-
                     (expt (fib (+ (truncate n 2) 1)) 2)
                     (expt (fib (- (truncate n 2) 1)) 2)))
   (t (+ (expt (fib (truncate n 2)) 2)
         (expt (fib (+ (truncate n 2) 1)) 2)))))

(fib (parse-integer (second *posix-argv*))) ;

하스켈

Lazy infinite list

 module Main where
 import System.Environment
 
 fibo = 1 : 1 : zipWith (+) fibo (tail fibo)
 
 main = do
     args <- getArgs
     print (fibo !! (read(args!!0)-1))

펄

하나의 예

 use bigint;
 
 my ($a, $b) = (0, 1);
 for (;;) {
     print "$a\n";
     ($a, $b) = ($b, $a+$b);
 }

Binary recursion, snippet

 sub fibo;
 sub fibo {$_ [0] < 2 ? $_ [0] : fibo ($_ [0] - 1) + fibo ($_ [0] - 2)}

Θ(F(n)) 실행 시간에 실행되며, Ω(1.6n)의 시간을 갖는다.

Binary recursion with special Perl "caching", snippet

 use Memoize;
 memoize 'fibo';
 sub fibo;
 sub fibo {$_ [0] < 2 ? $_ [0] : fibo ($_ [0] - 1) + fibo ($_ [0] - 2)}

Iterative, snippet

 sub fibo {
     my ($n, $a, $b) = (shift, 0, 1);
     ($a, $b) = ($b, $a + $b) while $n -- > 0;
     $a
 }

Command line iterative

 perl -Mbigint -le '$a=1; print $a += $b while print $b += $a'

포스트스크립트

Iterative

20 % how many Fibonacci numbers to print
                                                                               
1 dup
3 -1 roll
{
       dup
       3 -1 roll
       dup
       4 1 roll
       add
       3 -1 roll
       =
}
repeat

스택 리커전

This example uses recursion on the stack.

% the procedure
/fib
{
   dup dup 1 eq exch 0 eq or not
   {
      dup 1 sub fib
      exch 2 sub fib
      add
   } if
} def

% prints the first twenty fib numbers 
/ntimes 20 def
  
/i 0 def
ntimes {
   i fib =
   /i i 1 add def
} repeat

파이썬

재귀함수

def fibonacci(n):
	if 0 <= n <= 1:
		return n
	else:
		return fibonacci(n-1) + fibonacci(n-2)

def fibolist(n):
	list = []
	for i in range(n):
		list.append(fibonacci(i))
	return list

개선된 재귀함수 버전 (메모이제이션 적용)

fibomemo = {0:0, 1:1}
def fibonacci(n):
	if not n in fibomemo:
		fibomemo[n] = fibonacci(n-1) + fibonacci(n-2)
	return fibomemo[n]

def fibolist(n):
	fibonacci(n-1)
	return list(fibomemo.values())

For문

def fibonacci(n):
	a = 0
	b = 1
	for i in range(n):
		a, b = b, a+b
	return a

def fibolist(n):
	list = []
	a = 0
	b = 1
	for i in range(n):
		list.append(a)
		a, b = b, a+b
	return list

Generator

def fib():
   a, b = 0, 1
    while True:
        yield a
        a, b = b, a+b

행렬 방정식

def mul(A, B):
    a, b, c = A
    d, e, f = B
    return a*d + b*e, a*e + b*f, b*e + c*f

def pow(A, n):
    if n == 1:     return A
    if n & 1 == 0: return pow(mul(A, A), n/2)
    else:          return mul(A, pow(mul(A, A), (n-1)/2))

def fib(n):
    if n < 2: return n
    return pow((1,1,0), n-1)[0]

This calculates the nth Fibonacci number in O(log N) time, from the matrix equation

{\begin{bmatrix}1&1\\1&0\end{bmatrix}}^{n}={\begin{bmatrix}F\left(n+1\right)&F\left(n\right)\\F\left(n\right)&F\left(n-1\right)\end{bmatrix}}

and by using exponentiating by squaring.

스칼라

재귀함수

def fib(n:Int):Int = if (n <= 1) n else fib(n-1) + fib(n-2)

메모이제이션

val memo = collection.mutable.Map[Int, Int](0->0, 1->1)

def fib(n:Int):Int = {
        if (memo.get(n) == None) memo += (n -> (fib(n-1) + fib(n-2)))
        memo.get(n).getOrElse(0) 
    }

C언어/C++/자바/자바스크립트

Binary Recursive

 long fib(long n) {
   if (n < 2)
     return n;
   else
     return fib(n-1) + fib(n-2);
 }

Θ(F(n)) 실행 시간에 실행되며, Ω(1.6ⁿ)의 시간을 갖는다.

Tail-end Recursive

 long fib(long n) {
  return fibo_iter(n, 0, 1);
 }

 long fibo_iter(long x, long a, long b) {
  if (x==0) return a;
  else return fibo_iter(x-1, b, a+b);
 }

Θ(n) 실행 시간에 실행된다.

루비

 def fib(num)
   i, j = 0, 1
   while i <= num
     yield i
     i, j = j, i + j
   end
 end

 fib(10) {|i| puts i}

F#

꼬리 재귀호출(tail recursive call)

#light

let fibo n =
    let rec loop a b k =
        match k with
        | v when v <= 1 -> a
        | _ -> loop (a + b) a (k - 1)
    loop 1I 1I n

printfn "fibo(10) = %O" (fibo 10)

OCaml

 let rec fib n =
   if n > 2 then fib (n - 1) + fib (n - 2)
   else 1;;

 fib(10);;

로고

to fib :n
  if :n < 2 [output :n]
  output sum fib :n-1 fib :n-2
end

같이 보기