규칙을 발견해서 풀었다라고 보셨는데 그렇게 보실 수도 있지만 0과 1이 호출되는 횟수가 피보나치 수열을 이루는것은 수열 특성상 자연스럽게 그렇게 되는 것입니다

fibo(n)은 fibo(n)이 fibo(1)을 호출한 횟수와 같고 fibo(n - 1)은 fibo(n)이 fibo(0)을 호출한 횟수와 같은데

fibo(n - 1)에서 0을 호출한 횟수 + fibo(n - 2)에서 0을 호출한 횟수 = fibo(n)에서 0을 호출한 횟수이며

fibo(n - 1)에서 1을 호출한 횟수 + fibo(n - 2)에서 1을 호출한 횟수 = fibo(n)에서 1을 호출한 횟수입니다

호출 횟수를 나타내는 수열의 점화식이 피보나치와 같으니 당연히 피보나치 수열과 동일해지는 것입니다

fibo(1)에서 1호출횟수는 fibo(1)과 같고 0호출횟수는 fibo(0)과 같으므로 이를 초항으로 잡으면 됩니다

그리고 전역변수로 각각 카운팅하는 방법은 메모이제이션을 하지 않았을때 유효한 방법 아닐까요?

' fibo(n)은 fibo(n)이 fibo(1)을 호출한 횟수와 같고 fibo(n - 1)은 fibo(n)이 fibo(0)을 호출한 횟수와 같은데' 이 부분이 바로 이해가가지 않네요

혹시 왜 그런지 이유가 있을까요??

네 그리고 전역변수 카운팅은 메모이제이션을 하니 안되더라고요. 

네 그부분이 증명하고자 하는 명제입니다

편의상 fibo(n)이 0을 호출한 횟수를 A(fibo(n))으로 정의하고 fibo(n)이 1을 호출한 횟수를 B(fibo(n))으로 정의하겠습니다

그러면 명제는 다음과 같이 표현할 수 있습니다

임의의 자연수 n에 대하여, A(fibo(n)) = fibo(n-1)이고 B(fibo(n)) = fibo(n)이다

이 명제는 수학적 귀납법으로 증명할 수 있습니다

n이 1인 경우

A(fibo(1))은 0인데 fibo(0)도 0이므로 A(fibo(1)) = fibo(0)을 만족하며, B(fibo(1))은 1인데 fibo(1)도 1이므로 B(fibo(1)) = fibo(1)를 만족합니다

n이 2인 경우

A(fibo(2))은 1인데 fibo(1)도 1이므로 A(fibo(2)) = fibo(1)을 만족하며, B(fibo(2))은 1인데 fibo(2)도 1이므로 B(fibo(2)) = fibo(2)를 만족합니다

임의의 n에 대해서  n - 1과 n - 2가 명제를 만족하는 경우

우선 A(fibo(n)) = A(fibo(n - 1)) + A(fibo(n - 2))이고

B(fibo(n)) = B(fibo(n - 1)) + B(fibo(n - 2))인 것은 자명합니다

그리고 n - 1과 n - 2가 명제를 만족한다고 했으므로

A(fibo(n - 1)) = fibo(n - 2)이고 A(fibo(n - 2))는 fibo(n - 3)이므로 A(fibo(n)) = fibo(n - 2) + fibo(n - 3) = fibo(n - 1)입니다

마찬가지로

B(fibo(n - 1)) = fibo(n - 1)이고 B(fibo(n - 2))는 fibo(n - 2)이므로 B(fibo(n)) = fibo(n - 1) + fibo(n - 2) = fibo(n)입니다

따라서 모든 자연수 n에 대해서 해당 명제를 만족한다는 것을 알 수 있습니다

감사합니다~ 여러번 읽다보니 이해가 됐습니다!!

정말 감사합니다 ~