재귀 함수 : 자기 자신을 호출한다.

 뜬금없이 C언어 시간에 배우셨을 재귀함수를 왜 자료구조 카데고리에 쓸까요? 사실, 재귀 호출은, 스택을 이용한 것이거든요. 이번 시간에는 간단하게 팩토리얼 함수와 피보나치 함수 정도를 재귀로 어떻게 구현하는지 이야기 해 보도록 하겠습니다.

 

 재귀 함수는 아시다시피, 자기 자신을 호출하는 함수를 의미하는데요.

 

 

---

 

 팩토리얼 함수 f(x) = f(x-1)*x로 정의를 할 수 있어요. 그러면, 다음과 같이 작성할 수 있을 거에요.

 

 

 그런데, 이렇게만 작성을 하고 컴파일을 해서 프로그램을 실행시켜 보시면, 팩토리얼 5의 값이 나오지 않는 것을 알 수 있어요. 그냥 일정 시간동안 실행이 되다가, 종료가 되어 버리는 것을 알 수 있는데요.

 

 

 이건 왜 그럴까요? fact 함수 내부를 보면 x에다가 fact(x-1)의 값을 리턴하게 되어 있습니다. 즉, fact(x)가 값을 리턴하기 위해서는, fact(x-1)의 값이 리턴이 되어야 하고, fact(x-1)의 값이 리턴되기 위해서는, fact(x-2)의 값이 리턴되어야 합니다. 그런데 자세히 보면, fact를 호출 중단할 조건이 없어요.

 

 

 Main에서 fact(5)를 호출했어요. 그러면, fact(5)에서 fact(4)를 호출할 거에요.

 

 

 그런데 fact(4) 또한, fact(3)을 호출합니다. 이런 식으로 계속 호출을 할 겁니다. 자기 자신을 호출하지 않는 조건이 없기 때문입니다. 계속 call을 하다가, 스택이 꽉 차면 종료가 될 거에요.

 

 

 끝없이 호출하는 게 보이실 거에요. 이제 종료 조건을 넣어 봅시다.

 

 

---

 

 종료 조건은 간단한데요. 자기 자신을 부르지 않으면 됩니다. 보통, 특정한 값을 리턴해 버리고 바로 빠져나가게끔 합니다. x가 1보다 작을 때, fact를 다시 부를 필요가 없어요. 팩토리얼 0의 값도, 1의 값도 1이기 때문입니다. 그렇기 때문에, x가 1보다 작거나 같을 때에는, 그냥 1을 리턴해 주면 됩니다. 이렇게 했을 때, fact(5)를 호출하면 어떤 식으로 동작하는지 봅시다.

 

 

 f(2)가 리턴하라는 값은 f(1)에 2를 곱한 값이였습니다. f(1)를 호출한 결과가 1이 나왔습니다. 따라서, f(2)는 2에 1을 곱한 2를 돌려줄 겁니다.

 

 

 f(3)은 f(2)에 3을 곱한 값을 돌려주어야 할 겁니다. f(2)는 2를 돌려주었으니까, f(3)은 2에 3을 곱한, 6을 리턴하겠네요.

 

 

 f(3)이 6을 돌려주었습니다. f(4)는 f(3)에 4를 곱한 값을 돌려줄 건데요. 6에 4를 곱한 값은 24입니다.

 

 

 이제, f(4)의 리턴값 24를 활용해서 f(5)의 값을 계산해야 합니다. f(5)는 f(4)*5입니다. f(4)의 값이 24였고요. 24에다가 5를 곱한 값은 120입니다. 따라서, 최종적으로 fact(5)를 호출하면 120이라는 값이 리턴이 됩니다.

 

 

 

 정말 그런지, 코드를 한 번 실행해 볼까요?

 

 

 놀랍게도 120이 출력되었습니다.

 

 

---

 피보나치는 어떨까요? 피보나치 0번째 수는 1이고, 1번째 수 또한 1입니다. 따라서, x가 1보다 작거나 같다면, 그냥 1을 리턴해 버리게 하면 됩니다.

 

 

 여기까지는 그리 어렵지 않은 듯 싶네요. fibo(5)의 값은 8일 건데요. 저는 간단하게, fibo(4)의 값, 5를 구하기 위해서, 이런 식으로 코드를 짜면 어떤 식으로 호출이 되는지 보여드리도록 하겠습니다.

 

 

 먼저, f(4)를 구하기 위해서는 f(3)의 값과 f(2)의 값이 필요합니다. 그 중, 우리는 f(3)을 먼저 구해볼 겁니다.

 

 

 그런데, f(3)을 구하기 위해서는 f(2)와 f(1)의 값이 필요하다는 것이에요. f(2) 먼저 구해 봅시다.

 

 

 그런데 또 f(2)를 구하기 위해서는 f(1)과 f(0)의 값이 또 필요하네요. f(1) 먼저 구해 볼까요?

 

 

 종료 조건에 의해서 1이 리턴됩니다. 그 다음에 f(0)으로 가 볼까요?

 

 

 이것도 종료 조건에 의해서 1이 리턴됩니다. f(2)를 구하기 위해서 f(0)과 f(1)이 필요했는데, 이 두 값이 모두 1입니다. 두 값을 더한 값은 2이기 때문에, f(2)의 값은 2입니다. 따라서, 2를 돌려줍니다.

 

 

 f(3)을 구하기 위해서 f(2)와 f(1)의 값을 알아야 합니다. 그 중에서, f(2) 값은 구했으니까, f(1)을 구해 봅시다. 이 값은 종료 조건에 의해서 1이 나오게 됩니다.

 

 

 f(2)와 f(1)을 계산했기 때문에, f(3)을 계산할 수 있습니다. f(2)는 2, f(1)은 1이기에, f(3)은 3입니다. 그러면, f(4)를 알기 위해서, f(2)랑 f(3)을 알아야 할 건데요.

 

 

 f(3)은 3이였습니다. 남은 건 f(2)인데, fibo(2)의 값을 저장했나요? 아닙니다. 그렇기 때문에, fibo(2)를 계산하기 위해서, 다시 f(0)과 f(1)의 값이 필요하게 됩니다. 뭔가 비효율적인 것이 보이시나요?

 

 

 fibo(2)는 다시 계산할 필요가 없어요. 그런데도, 다시 계산하고 있어요. 이는 f(3)을 호출했을 때, f(2)도 호출을 했을 텐데요. 이 때, f(2)의 값을 저장하지 않고 바로 리턴해 버렸기 때문이에요. 이런 식으로 하면 f(45)을 구하는 데 시간이 상당히 많이 걸릴 겁니다. 실제로 fibo(45)를 구하는 데 걸리는 시간을 간단하게 clock 함수를 이용하여 측정해 보았습니다.

 

 

 9.73초나 걸렸어요. 분명한 것은 fibo[x]의 값을 저장하면, 이러한 비효율적인 호출은 줄어들 수 있다는 것입니다. 메모이 제이션을 한다고 하는데, 알고리즘 파트에서 자세하게 이야기를 해 볼 기회가 있을 듯 싶습니다. 이 포스팅에서는 그리 중요하지는 않아요. 오늘은 재귀 함수에 대해서 간단하게 해 보았어요. 자기 자신을 호출하는 함수는 끝나는 조건이 있어야 한다. 정도만 기억하시고 있으면 됩니다.