알아 보기

 

러시아 인형을 떠올리면서 프로그램 4-2를 해석해 볼까요?

우선 n이 1 이하인지 비교합니다. 1 이하(0 포함)는 아주 작아서 더는 계산하지 않아도 되는 ‘종료 조건’입니다(러시아 인형에서 가장 작은 마지막 인형에 해당합니다). 이때 1을 결괏값으로 돌려줍니다(마지막 인형 안에 들어 있는 달콤한 사탕에 해당합니다).

n이 1보다 크면 n! = n × (n - 1)!이므로 n * fact(n - 1)을 결괏값으로 돌려줍니다. 이 과정에서 n!을 구하기 위해서 약간 더 작은 값인 (n-1)!을 구하는 fact(n - 1)이 재귀 호출됩니다(인형 안에 들어 있는 조금 더 작은 인형에 해당합니다).

여기서 궁금증이 하나 생깁니다. fact(n)을 풀기 위해서 fact(n - 1)을 재귀 호출하였는데 호출된 fact(n - 1)은 어떻게 실행될까요?

다시 종료 조건에 해당하는지 확인합니다. 종료 조건이 아니라면 이번에는 fact(n - 2)를 호출합니다. 마찬가지로 fact(n - 3), fact(n - 4)… 이렇게 반복하다 보면 결국 fact(1)을 만나게 됩니다. 따라서 재귀 호출이 영원히 반복되지 않고 결국 답을 얻게 됩니다.

어떤가요? 조금 헛갈리지만 어떻게 계산되는지 알 것도 같습니다. 좀 더 확실히 이해하기 위해 fact(4)를 호출했을 때를 생각해 봅시다.

 

1 | fact(4)는 4 * fact(3)이므로 fact(3)을 호출하고

2 | fact(3)은 3 * fact(2)이므로 fact(2)를 호출하고

3 | fact(2)는 2 * fact(1)이므로 fact(1)을 호출합니다.

4 | fact(1)은 종료 조건이므로 fact() 함수를 더 이상 호출하지 않고 1을 돌려줍니다.

5 | fact(2)는 fact(1)에서 돌려받은 결괏값 1에 2를 곱해 2를 돌려주고

6 | fact(3)은 fact(2)에서 돌려받은 결괏값 2에 3을 곱해 6을 돌려주고

7 | fact(4)는 fact(3)에서 돌려받은 결괏값 6에 4를 곱해 24를 돌려줍니다(최종 결과).