재귀는 왜 어려울까? 내 머리속의 재귀 모델
재귀에 대한 내 머리속 모델은 이렇다.
"아직 모르는 것"을 함수 호출로 표현한다.
이게 끝이다. 올 ㅋ
팩토리얼의 예를 보자. C로 짜봤다.
int factorial(int n)
{
int ret = 1;
for(int i = 1; i <= n; i++){
ret *= i
}
retrun ret;
}
명령형으로 짠 팩토리얼이다.
int factorial(int n)
{
if (n == 1)
return 1;
return n * factorial(n - 1);
}
재귀로 짠 팩토리얼이다.
생각의 모델
두 표현의 가장 큰 차이점이 뭘까?
재귀는 아직 모르는 것을 함수 호출로 표현했다는 점이 가장 큰 차이점이다.
명령형에서 우리는 n번째 팩토리얼을 1번째부터 쌓아나가면서 계산한다. (그런 생각이 표현되어 있다)
명령형은 아래에서부터 위로 계산한다.
즉 ret는 1 -> 2 -> 6 -> 24 -> 120 -> ... 이렇게 쌓아나간다.
그런데 재귀는 생각하는 방식 자체가 다르다.
재귀 코드는 위에서부터 아래로 계산한다.
즉 가장 먼저 n번째 팩토리얼을 계산하려 든다.
n번째 팩토리얼을 어떻게 계산하는가?
정수 n과 n-1번째 팩토리얼을 곱하면 된다.
그런데 n-1번째 팩토리얼을 모르는데? 그것은 함수가 알아서 해 줄 것이다.
이런 생각으로 짜여진 코드이다.
즉 재귀 코드는 n - 1 번째 팩토리얼을 "아직 모르는 것" 으로 생각하고 계산을 함수 그 자체에 맡긴다.
이런 생각 자체가 명령형에 익숙한 프로그래머들에게는 매우 이질적이다.
생각하는 방식 자체를 바꿔야 하기 때문에 재귀가 어렵다.
위에서 제시한 모델로 생각을 하면 의외로 쉽게 재귀 코드를 짤 수 있다.
또한 어떤 알고리즘은 재귀가 쉬운데, 어떤 알고리즘은 명령형이 쉬운 이유가 이 때문이다.
명령형 패러다임이 어울리는 알고리즘은 재귀 호출에서와 같은 "아직 모르는 것"이 없다.
달리 말하자면, 명령형은 "아직 모르는 것"을 표현하기 어렵다.
몇몇 알고리즘을 명령형으로 짜는게 어려운 이유가 바로 이 때문이다.
ㅈ도 모르면서 재귀 내려치기 하지 마라
초보 프로그래머는 "아직 모르는 것"이 등장하는 알고리즘을 짤 일이 드물어서 재귀적인 사고방식의 쓸모를 알기 힘들다.
흔히들 C언어로 입문한 김치국 컴공 1학년은
재귀를 배우면서 팩토리얼, 피보나치, 잘 하면 하노이의 탑을 배운다.
이 3가지 알고리즘에서 "아직 모르는 것"을 이용하여 표현하는게 자연스러운 알고리즘은 무엇인가?
하노이의 탑 밖에 없다.
다른 두 가지, 특히 피보나치는 "아직 모르는 것" 메타를 쓰면 시간/공간 복잡도가 폭★발한다.
문제는 가르치는 놈이 재귀할 줄 몰라서 끠보나치까지만 보여주면서
재귀는 쓰레기니 쓰지 말라고 하는 분들이 있다는 거겠지..
결론
재귀와 명령형은 생각을 표현하는 방식이다. 그리고 각자 장단점이 있다.
명령형은 값을 쌓아나가는 알고리즘을 표현하기 매우 쉽다.
그러나 명령형으로 "아직 모르는 것"을 표현하려면 보통 큐나 스택 등 추가적인 자료구조가 필요하다.
재귀는 "아직 모르는 것"을 표현하는 것이 매우 자연스럽다.
그러나 재귀로 명령형의 그것을 표현하려면 꼬리재귀를 사용해야 한다.
추가
https://youtu.be/k8bI3b-GUs8
https://youtu.be/KSMy52drZa8
뉴비들에게 재귀를 이렇게 가르치면 안 된다.
위 설명은 너무 저수준으로 접근하고 있다.
틀린 말은 없지만 재귀적 사고방식의 핵심을 설명하지 않고
재귀를 "명령형 사고방식"으로 설명하고 있다.
그러나 대부분의 뉴비들은 재귀를 처음 접할 때 이런 설명을 듣게 되는게 현실이다...
추가 2
"아직 모르는 것" 예시 문제: https://codingdojang.com/scode/417?answer=29098#answer_29098
오랜만에 재귀하니 재밌다!