0. 인트로
재귀란 무엇인지를 알고싶으면 여기를 클릭하면 된다.
여기를 클릭했는데 계속 같은 곳만 클릭이 되고, 짜증이 나고, 멈춰라는 말이 떠오르면 멈추면 된다. 재귀를 설명하라고 했더니 갑자기 이상한 농담을 한다고 한다면, 아래 링크를 가시면 된다. 실제로 구글신께서는 여기 본문과 같은 형식으로 재귀를 설명하고 있다.
https://www.google.com/search?q=recursion
1. 재귀의 정의와 쓰임새
재귀란 하나의 함수에서 자신을 다시 호출하여 작업을 수행하는 방식으로 주어진 문제를 푸는 방법을 뜻한다. 즉, 재귀는 일종의 반복 알고리즘이라고 볼 수 있다. 사실 재귀가 어렵기는 한데, 반복문을 쓰면 로직이 어려워 질 경우에는 울며 겨자먹기로 재귀를 써야된다. 반복문을 쓰면 로직이 어려워 지는 경우가 중첩된 반복문이 많거나 반복문의 중첩 횟수(number of loops)를 예측하기 어려운 경우에 해당된다.
2. 재귀와 시간복잡도
사실 이 블로그에서 예전에 배열 part에서 피보나치 수열을 JavaScript로 작성한 적이 있다. https://velog.io/@porupit0122/JS-%ED%94%BC%EB%B3%B4%EB%82%98%EC%B9%98-%EC%88%98%EC%97%B4
모든 반복문은 재귀 알고리즘으로 작성 가능하기 때문에 피보나치수열을 재귀를 이용하여 작성하도록 하겠다.
재귀를 사용할 때는 기저 조건을 설정하지 않으면 무한 뺑뺑이로 인하여 에러가 난다.(maximum call stack exceed ㅂㄷㅂㄷ) 따라서, 종료 조건에 해당되는 기저조건을 잘 설정하는 것이 중요하다. 0과 1으로 시작되는 피보나치 수열의 경우라면 기저조건은 다음과 같을 것이다.
function fibonacci(n) {
// base case
if (n <= 1) {
return n;
}즉, n이 1 이하면 그대로 입력된 값을 리턴하는 것이 기저조건이다. 이제는 재귀(반복) 조건을 적어주면 된다. n이 2이상인 경우, 피보나치 수열은 전전값과 전값의 합이 리턴값이다. 따라서 피보나치 함수에 1작은 값을 넣은 것과 2작은 값을 넣은 것의 합을 리턴해야 된다는 사실을 알 수 있다. 따라서 코드는 다음과 같다.
function fibonacci(n) {
//base case
if (n <= 1) {
return n;
} else if (n>=2) { // recursive case
return fibonacci(n-1) + fibonacci(n-2);
}
}그러나 이 함수는 치명적인 문제가 있다. 시간복잡도는 Big O의 의 계수법칙에 의하여 O(2^n)이다.(실제 복잡도는 O(2^(n-1))임) n이 10만 되도 512번이나 반복하는 것이다. 그 이유는 n이 2 이상이면, 한 함수에 재귀 호출이 두번이나 일어나기 때문이다.
n = 0 : 함수호출 1번
n = 1 : 함수호출 1번
n = 2 : fibo(1)과 fibo(0) 호출(2번)
n = 3 : fibo(2)와 fibo(1), fibo(0) 호출(4번 = 2^(3-1))
...
3. 꼬리 재귀함수와 피보나치 수열
꼬리 재귀(tail recursion)함수란 재귀 호출이 함수에서 가장 마지막에 실행되는 방식의 재귀함수이다. 피보나치 수열은 수열이 이어짐에 따라서 전전값과 전값이 바뀐다. [0,1,1,2,3,5, ...]에서 2번째 인덱스 이상을 기준으로 하면 전전값과 전값이 (0,1) => (1,1) => (1,2)로 계속 변한다. 그 값은 (전전값, 전값) => (전값, 전전값 + 전값) 꼴로 변한다. 이러한 반복꼴을 이해한다면 재귀함수 리턴값을 하나만 해도 된다. 아래는 꼬리 재귀를 이용한 자바스크립트 코드이다.
function fibonacci(n, lastlast = 0, last = 1) {
// base case
if (n == 0) {
return lastlast;
} else if (n == 1) {
return last;
}
return fibonacci(n-1, last, lastlast+last);
}
