[Swift] Data Structure Recursion / Fibonacci / 자료구조 재귀, 순환 / 피보나치 수열

 

dbguswls030/Argorithm

 

재귀 호출로 구현할 수 있는 가장 대표적인 예 중 하나가 피보나치 수열이다.

 

앞의 두 개의 숫자를 더해 뒤의 숫자를 만들면 된다.

 

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89....

 

 

func fib(_ n: Int) -> Int{
    if n == 0{
        return 0
    }
    else if n == 1{
        return 1
    }
    else{
        return fib(n-1) + fib(n-2)
    }
}

이 함수는 단순하고 이해하기 쉽게 재귀 호출로 구현되었지만 사실 매우 비효율적이다. 그 이유는 무엇일까?

 

 

fib(6)이 호출하면 fib(4)가 두 번 반복하여 호출된다.

 

 

fib(6)

= fib(4) + fib(5)

= fib(2)+fib(3) + fib(3)+fib(4)

= fib(0)+fib(1) + fib(1)+fib(2) + fib(1) + fib(2) + fib(2)+ fib(3)

= fib(0)+fib(1) + fib(1)+fib(0)+fib(1) + fib(1) + fib(0) + fib(1) +fib(0) + fib(1)+ fib(1) + fib(2)

= fib(0)+fib(1) + fib(1)+fib(0)+fib(1) + fib(1) + fib(0) + fib(1) +fib(0) + fib(1)+ fib(1) + fib(0) + fib(1)

 

트리 구조로 시각화해야 이해하기 쉽지만 ..... 대충....

 

 

이런 현상은 재귀 호출이 깊어질수록 점점 심해질 것이도 상당히 비효율적이다. 이러한 현상의 근본적인 이유는 중간에 계산된 값을 기억하지 않고 다시 계산하기 때문이다. 

 

해결 방안으로는 메모이제이션이라고 하는 기법이다. 다음에 Araboza