Tip:
Highlight text to annotate it
X
(번역 : Jisoon Lim) 이번 비디오에서는,
재귀적 피보나치 함수를 단계별로 이해하는 시간을 가져보죠.
재귀적 피보나치 함수를 단계별로 이해하는 시간을 가져보죠.
자, 인수 5를 넣어서 함수를 호출한다고 합시다.
자, 인수 5를 넣어서 함수를 호출한다고 합시다.
너무 큰 숫자를 정하면 이거 하루 종일 설명해도 모자라니까 ...
너무 큰 숫자를 정하면 이거 하루 종일 설명해도 모자라니까 ...
fibonacci(5) ... 를 호출하고,
자, 이 상황에서 함수에 들어가면
여기 매개변수 n 은 5 와 같고,
그래서 첫 경로에서 n 은 5 죠.
여기 코드를 보면 n 이 2 보다 작을 때 n 은 반환하는 데,
여기 코드를 보면 n 이 2 보다 작을 때 n 은 반환하는 데,
5 는 당연히 2 보다 크니까
else 구문으로 들어가서,
else 구문으로 들어가서,
fibonacci(n - 1) + fibonacci(n - 2) 를 반환합니다.
결국 이걸 호출하는 행위는 ...
뭐, 생각하기에 따라서, 간단하게 표현되는데,
기대하는 n, 즉 5 의 피보나치 수를 반환하게 됩니다. 왜냐 ..
기대하는 n, 즉 5 의 피보나치 수를 반환하게 됩니다. 왜냐 ..
n - 1 은 4 고,
n 이 5 니까 n - 2 는 ...
5 - 2 니까 3 ...
뭐, 일단 함수 호출이 더 많아지긴 했는데
차근차근 다 해보지요.
이번엔 n 이 4 와 3 이 됐죠.
그러니까 이번엔 ...
여기 n 은 4 고 ...
n 이 4 니까 ...
4 는 2 보다 크니까 ...
이 부분은 무시하고 ...
else 구문으로 가서 ...
이걸 반환하겠죠. 일단 fibonacci(4 - 1) 니까 ...
간소화해서 쓰면 ...
간소화해서 쓰면 ...
fibonacci(3) 에다
fibbonacci(4 - 2) 니까
fibbonacci(2) 를 더해서
결국 이게 반환하는 값이 되죠.
그리고 이쪽 fibonacci(3) 은 ...
음, 헷갈리니까 이쪽을 좀 묶어주죠.
자, 이놈은 이 자홍색 부분을 반환하고
이놈은 녹색으로 된 놈을 반환할 겁니다.
n 이 3 이고, 2 보다는 크니까
이쪽에서 ...
이번에 반환할 값은 fibonacci(3 - 1) 이니까 fibbonacci(2) ...
더하기 fibonacci(3 - 2) 니까 fibonacci(1) 을 더하고
그리고 이쪽으로 건너와서,
얘네들도 다 풀어봅시다.
결국 계속 fibonacci 를 호출하는 거죠.
자, fibonacci(3) 이면 ... 이제 어떻게 돌아가는지 대충 감이 올 텐데요,
자리가 모자라니까 fibonacci 를 fib 으로 줄여쓸게요 ...
자리가 모자라니까 fibonacci 를 fib 으로 줄여쓸게요 ...
fibonacci(3) 을 호출하면
n 은 3 이고 2 보다 크니까
fib(3 - 1) 에다가 ...
fib 이 fibonacci 입니다.
fib(2) 더하기 fib(3 - 1) 니까
fib(1) 을 더한 거죠.
이렇게 되고죠,
그리고 여기 fibonacci(2) 는 ...
2 는 2 보다 작지 않으니까,
반환할 값은 ... fib(2 - 1) 이니까
fib(1) 더하기 fib(2 - 2) 면 ...
fib(0) 을 더하는거죠.
이렇게 2 개의 피보나치 호출이 되었고요,
이쪽의 fibonacci(2) 도 똑같아요.
fibonacci(2) 를 호출하면
왼쪽의 fibonacci(2) 와 마찬가지로
fib(1) + fib(0) 의 2 개의 호출이 될 거고요,
fib(1) + fib(0) 의 2 개의 호출이 될 거고요,
그리고 fibonacci(1) 입니다. 이게 재밌는데
그리고 fibonacci(1) 입니다. 이게 재밌는데
왜냐면 n 이 1 이니까요,
갑자기 이 조건이 참이 됩니다.
n 이 2 보다 작으니까, n 을 반환해야 되죠.
그럼 이건 어떻게 되냐면
이 부분이 1 이 됩니다.
돌려보니 1 이 돼요.
그리고 이쪽으로 건너오면,
fib(2) ... 아까 한 대로면 fib(2) 는 fib(1) + fib(0) 이죠.
그러니까 이렇게 ...
fib(1) + fib(0) 을 써주고요.
fib 은 fibonacci 에요 ...
그리고 이 fib(1) 도 이제 알죠.
1 은 2 보다 작으니까 n 을 반환하면 ...
이건 1 을 반환합니다.
fib(1) 은 1 을 반환해요.
그리고 fib(0) 는 ...
0 이 2 보다 작으니까, 0 을 반환해서 ...
fib(0) 은 0 입니다.
fib(0) 은 0 을 반환하고,
fib(1) 은 1 을 반환해요.
이 fib(0) 도 0 을 반환하고,
여기 fib(1) 도 1 을 반환해요.
이 fib(0) 도 0 을 반환해요.
결국 지금까지 인터프리터는 이 재귀적 함수 호출을 처리한 거고,
이게 결국 이 흐름을 전부 기억하고 처리하는 겁니다.
왜냐면, 언젠가 n 이 1 이나 0 이 되기만 하면 이 기본 케이스에 도달할 테니까,
왜냐면, 언젠가 n 이 1 이나 0 이 되기만 하면 이 기본 케이스에 도달할 테니까,
결국은 상수값을 반환한 후에 이 흐름을 따라서 올라갈 수 있게 되지요.
결국은 상수값을 반환한 후에 이 흐름을 따라서 올라갈 수 있게 되지요.
그래서 여기 fib(2) 는 ... 1 + 0 이니까
그래서 여기 fib(2) 는 ... 1 + 0 이니까
fib(2) 는 1 입니다.
여기 fibonacci(3) 는 fib(2) + fib(1) 인데,
이게 1 이니까 ...
1 + 1 이 되어서 ...
결국 2 겠군요.
이쪽 fibonacci(2) 를 보면 ...
fib(1) + fib(0) 이니까 1 이고요.
fibonacci(2) 는 ... 1 + 0 이니까 1 이죠.
fibonacci(2) 는 ... 1 + 0 이니까 1 이죠.
이쪽 fibonacci(1) 은 1 이에요.
자, 그럼 윗 단계로 올라가서,
이렇게 맨 처음의 함수 호출로 회귀해가는 겁니다.
어떻게 인터프리터가 이걸 다 처리하는지는 지금은 얘기하지 않을게요.
어떻게 인터프리터가 이걸 다 처리하는지는 지금은 얘기하지 않을게요.
굉장히 재밌는 이야깃거리이긴 한데, 지금은 이 재귀함수의 흐름을 집중해서 이해하고
굉장히 재밌는 이야깃거리이긴 한데, 지금은 이 재귀함수의 흐름을 집중해서 이해하고
어떻게 해서 이게 돌아가는지 아는 게 중요하니까요.
어떻게 해서 이게 돌아가는지 아는 게 중요하니까요.
자, 이쪽의 fibonacci(4) 를 보면
음, 피보나치 수열의 4 번째 항은 ...
3 번째 항과 2 번째 항의 합과 같죠.
그런데 우린 이미 여기서 그게 각각 2 와 1 인 걸 알았으니까, 그냥 더해서 3 이란 걸 알 수 있네요.
그런데 우린 이미 여기서 그게 각각 2 와 1 인 걸 알았으니까, 그냥 더해서 3 이란 걸 알 수 있네요.
3 번째 피보나치 수는, 피보나치 수열의 정의를 따르면
1 번째 항과 2 번째 항의 합과 같지요.
여기 그 각각이 있고, 그 합은 1 + 1 이니까 2 군요.
여기 그 각각이 있고, 그 합은 1 + 1 이니까 2 군요.
그럼 5 번 항, 피보나치 수열 5 번째 항은 ...
그럼 5 번 항, 피보나치 수열 5 번째 항은 ...
4 번째 항과 3 번째 항의 합이니까 ...
각각 3 과 2 고 ...
3 + 2 니까 5 로군요.
결국 이 녀석은 5 로 밝혀졌습니다.
자, 이렇게 하면 재귀적 프로그램이 어떻게 돌아가는 지 좀 이해가 오나요?
자, 이렇게 하면 재귀적 프로그램이 어떻게 돌아가는 지 좀 이해가 오나요?
이게 참 정교한 게 ...
만약 이 밑에서 fibonacci(1) 과 fibonacci(0) 에 대한 기본 케이스를 정의하지 않았다면,
만약 이 밑에서 fibonacci(1) 과 fibonacci(0) 에 대한 기본 케이스를 정의하지 않았다면,
이 함수는 자기 호출을 영원히 반복했을 겁니다.
재귀문의 핵심은, 자기 자신을 몇 번이고 호출하면서
재귀문의 핵심은, 자기 자신을 몇 번이고 호출하면서
기본 케이스를 향해 내려가는 겁니다.
그러면 어느 시점에서,
자기 호출하다가, 자기 호출하다가,
결국은 이 호출들이 기본 케이스로 돌입하고,
결국은 이 호출들이 기본 케이스로 돌입하고,
여기서부터 실제 값을 구축해 올라갑니다.
그렇게 동작하는거죠.
모든 fibonacci 호출은 결국 낮은 n 값의 fibonacci 호출로 정리되고,
모든 fibonacci 호출은 결국 낮은 n 값의 fibonacci 호출로 정리되고,
n 값은 계속 줄어들면서 기본 케이스로 다가갑니다.
그리고 실제 값을 전달해서, 이전의 호출들을 값으로 재구성하게 해주는 거죠.
그리고 실제 값을 전달해서, 이전의 호출들을 값으로 재구성하게 해주는 거죠.
좀 도움이 됐나요?
재귀문은 어렵긴 한데,
나름대로 굉장히 우아하고 멋진 알고리즘입니다.
나름대로 굉장히 우아하고 멋진 알고리즘입니다.