[재귀 함수]피보나치 함수 코드

Recursive Thinking : 피보나치

재귀 함수를 짜는 연습을 하기 좋은 함수형 언어를 사용해서 재귀적 사고를 연습해 보았다.
함수형 언어의 이념에서는 기본적으로 for를 지원하지 않기 때문에 반복적인 작업들을 모두 재귀 함수를 사용해서 작성해야 한다.

피보나치 수열

Naive

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

가장 간단하게 짜는 피보나치 수열함수이다. 아마 프로그래밍을 시작하고나서 접해보는 가장 간단한 리컬시브 함수가 아닐까한다.

코드도 짧은데 뭐가 문제일까.

Naive 피보나치 함수는 코드가 간단하지만 시간복잡도가 지수 함수를 갖기 때문에 n = 100만 되어도 엄청난 시간이 걸려 수행을 멈추게 된다. 이는 수 많은 중복 호출이 있기 때문인데 이를 해결하는 방법으로는 크게 메모이제이션과 Bottom - up 방식이 있다. 하지만 for를 사용하지 않고 재귀함수를 주로 사용하는 함수형 언어에서는 Bottom -up 방식을 두 가지 방법으로 구현할 수 있는데 이를 살펴보고 Tail - recursion으로 메모리를 사용을 크게 줄이는 방법도 알아보려고 한다.

시간 복잡도 줄이기

Bottom up 방식을 for를 쓰지않고 스택을 사용해서 위에서 부터 내려가는 방법을 구현할 수 있다.

def fib2B(n: Int) : BigInt = {  
  
  def _fib2B(n: Int) : (BigInt, BigInt) = {  
    if (n == 2) (1, 1)  
    else {  
      val (x, y) = _fib2B(n-1)  
      (x + y,  x)  
    }  
  }  
  if (n <= 2) 1  
  else  
  {  
    val (x, _) = _fib2B(n)  
    x  
  }  
}  

메모리 사용 줄이기 : Tail recursion

위에서 사용한 방법은 메모리 스택을 쌓기 때문에 n = 10000을 넘어가면 메모리 용량을 초과하는 스택 오버 플로우 에러가 발생한다. Tail recursion이란 recursive 함수를 부를 때 계산을 유보하지 않고 다음 함수에 계산된 값을 집어넣어 스택을 추가적으로 남겨놓지 않는 방법이다. idx 라는 값을 하나 집어넣어주면 대부분의 리컬시브 함수를 Tail recursion으로 바꿔줄 수 있다.
다음의 Tail recursion을 사용해 스택에 제한없이 fib3C(1000)

import scala.annotation.tailrec  


def fib2C(n: Int): BigInt = {  
  @tailrec  
  def fib2C(idx: Int, current: BigInt, past1: BigInt): BigInt = {  
    if (n == idx) current  
    else _fib2C(idx + 1, current + past1, current)  
  }  
  if (n <= 2) 1  
  else _fib2C(2, 1, 1)  
  
}