이번에도 역시 종료 상태(호출한 함수에 전달한 인수 n이 3보다 작은지)부터 검사했다. 그래서 종료 상태라면 1을 리턴하고, 그렇지 않다면 fib(n-1)을 호출한 결과와 fib(n-2)를 호출한 결과를 더한 값을 리턴한다.

그림 7-3은 fib를 작은 값(4)으로 호출한 과정을 보여 준다. 이 과정은 세 단계로 진행되며, 각각 동일한 함수에 인수만 바꿔서 계속 호출하는 방식으로 실행된다. 식 (7.5)는 두 피보나치 수에 대해 진행하므로 gcd2보다 재귀호출 과정이 훨씬 복잡하다. 특히 종료 상태에 대한 말단 호출(leaf call)이 세 개나 있는데, 이 단계에서는 더 이상 재귀적으로 호출되지 않는다.^{Exs 1}

▲ 그림 7-3 fib(4)에 대한 재귀 호출 과정