[baekjoon 10872번, 10870번] 재귀 - 팩토리얼, 피보나치

1. 팩토리얼

 

팩토리얼 수식 : n! = (n-1) x (n-2) x (n-3) x ... x 2 x 1

 

팩토리얼을 재귀 함수로 푼 결과와 동적 계획법으로 푼 결과이다. 너무 쉽기 때문에 설명은 생략하겠다.

 

2. 피보나치

 

n번째 피보나치 수는 바로 앞 두 피보나치 수(n-1번째 항, n-2번째 항)의 합이 된다. 이를 수식으로 표현하면 아래 수식과 같다.

 

그렇다면

a₂ = a₀ + a₁
a₃ = a₁ + a₂
a₄ = a₃ + a₂
.
.
.
aₙ = aₙ₋₁ + aₙ₋₂

 

이렇게 나아간다.

 

그렇다면 위 수식의 방식으로 a₆을 구해보자

 

a₂ = a₀ + a₁ = 0 + 1 = 1
a₃ = a₁ + a₂ = 1 + 1 = 2 
a₄ = a₂ + a₃ = 1 + 2 = 3
a₅ = a₃ + a₄ = 2 + 3 = 5
a₆ = a₄ + a₅ = 3 + 5 = 8

위 수식들처럼 되는 걸 알 수 있다.

 

따라서 피보나치 함수를 설계할 때 aₙ을 구하려면 aₙ₋₁과 aₙ₋₂를 더하는 것을 (n+1)-2번 반복해야 하는 것을 확인할 수 있다.

 

왜 n+1이냐면 피보나치 수는 0부터 시작하기 때문에 n번째 항을 구하려면 그 이전 n개의 항들을 알아야 하기 때문에 n번째 항 + (이전 항들의 갯수=n) = n+1이기 때문이다.

 

또한 우리는 이미 a₀과 a₁을 알고 있기 때문에 2개의 항은 계산할 필요가 없으므로 (n+1)-2 = n-1번을 반복하면 된다.

 

이걸 for문으로 짜는 것은 매우 직관적이고 알기 쉽다. 하지만 재귀함수로 짠다는 건 매우 복잡하고 머리가 아픈일이다.

왜냐하면 재귀함수를 호출했을 때 그 안에서 값들이 어떻게 변할지 예측하는 것이 매우 어렵기 때문이다. 

 

여러 변수의 각 과정을 눈으로 보지 않고 머리속으로 상상해서 예측한 뒤 재귀함수에 필요한 매개변수나 동작 코드들을 작성한다는 것은 상당히 어려운 과정이다.

 

사실 그래서 나도 이 피보나치 함수를 재귀함수로 짤 때 찍어서 맞췄었다. 어떻게 찍었냐면 

 

aₙ = aₙ₋₁ + aₙ₋₂ = (aₙ₋₂ + aₙ₋₃) + aₙ₋₂ = ...

 

피보나치 수는 위와 같은 수식으로 계속해서 진행한다. 여기서 aₙ₋₃ = 첫 번째항, aₙ₋₂ = 두 번째항으로 둔다면

네 번째 항 = 두 번째항 + (첫 번째항 + 두 번째항)이 된다.

 

그래서 피보나치 함수의 매개변수에 첫 번째 항과 두 번째 항을 a와 b로 받고 또 피보나치 함수를 호출할 때는 b, a+b를 넘겨주었다. 그랬더니 그냥 원하는 결과가 나왔었다. 

 

다 풀고나서 왜 그랬는지 하나하나 설명해주는 것은 쉽지만 아무것도 모르는 상태에서 피보나치 수들만 가지고 재귀함수의 매개변수와 인자를 예측해서 코딩하는 것은 너무 어려운 일인 것 같다.

 

그래서 코드도 아래와 같다.

 

fibonacci dynamic에서 a와 b인자는 받을 필요가 없이 그냥 함수내에서 0과 1을 주면 된다. 그런데 assert문으로 재귀함수와 같이 값을 비교할 때 인자들이 없으면 뭔가 허전해서 그냥 넣어뒀다.

 

위 그림과 같이 코드를 작성하고 나서 똑같이 수를 넣고 돌려보다가 재귀함수의 치명적 단점을 발견하였다.

 

재귀함수는 반복하는 횟수가 커지면 저렇게 stackoverflowerror를 발생시킨다. 아무래도 계속해서 함수를 호출하기 때문에 그만큼 스택이 계속 쌓일 것이고 그에 따라 예외처리를 하지 않으면 저렇게 에러를 출력하고 프로그램을 종료하게 된다.

 

반면에 동적 계획법을 사용한 방식은 우리가 넘겨주는 수의 자료형을 int로 설정했기 때문에 int의 최댓값을 넘지 않는다면 속도도 빠르고 에러 발생도 없이 원하는 결괏값을 잘 출력해줄 수 있었다.