Recursion
최근 업무를 하던 도중 노드의 트리구조를 Recursion 을 사용해서 구현하는 코드를 보고 충격을 받았다.
재귀 구조를 해석하는데에 (프로세스를 머리로 돌리는데) 상당시간 걸렸다는 점(창피하지만), 그리고 상당히 코드가 깔끔했다는 점.
웹 서비스 개발의 경우 복잡 다단한 알고리즘이 필요 없을것이라 합리화하며 문제풀이(알고리즘) 학습에 손을 놨던 지난날의 나를 반성하며 조금씩 알고리즘 학습을 시작중이다.
문제를 풀면 풀수록 머리가 아프지만, 어렵지만 더 나은 개발자가 되기 위한 고통의 과정이라고 확신하며 오늘도 몸서리 친다. 특히나 예전부터 항상 나의 발목을 잡았던 그놈의 재귀 에 대한 고찰을 옮겨 적어본다.
재귀에 대한 고찰
알다시피 많은 수의 프로그래밍 서적을 보면 어떤 문제의 해결에 있어서 for, while 과 같은 반복을 먼저 가르치고 recursion 은 그 순서나 중요도를 뒤로 보내는 경우가 많다.
때문인지 재귀를 보는 순간 많은 사람들이 어렵다 라거나 복잡하다 라고 생각하는 경우가 부지기수다.
그러나 재귀는 그렇게 어렵거나 복잡한 문제가 아니고 많은 수의 문제 해결에 있어서 핵심적이고 중추적인 역할을 하는 경우가 많다.
재귀는 어려워서는 안되고, 재귀를 이용하는 방법은 연습을 통해 충분히 습득할 수 있다.
마치 for문이나 while문을 통한 문제 해결이 반복적인 연습을 통해 익숙해진 것 처럼.
왜 재귀를 사용하는가.
재귀를 이해하기 위해서는 재귀를 이해해야 한다는 농담이 있다.
이는 재귀의 핵심적인 정의인 어떤 함수가 자기 자신을(자기 자신과 비슷한) 함수를 호출한다 는 것과 깊은 관련이 있다.
그렇다면 재귀 함수가 자기 자신을 호출한다는 것에는 어떤 의미가 있는 것일까?
그 의미는 바로 재귀 함수가 자신을 호출할 때에는 언제나 더 간단해진 문제를 넘겨준다 에 있다.
다시말해 재귀함수에 의해 호출되는 함수는 점점 더 간단해진 문제를 해결한다는 뜻이다.
그리고 이렇게 문제는 점점 더 간단해 지다가 손쉽게 해결할 수 있게 되고 이 때 재귀는 끝을 맞이하게 된다.
이제 위에서 말했던 것의 의미를 탐구해 보자.
다음과 같은 중첩 리스트의 원소들을 모두 합하는 함수를 생각해 보자.
[1,[11,42,[8,1],4,[22,21]]]
이 함수는 다음과 같은 결과를 가질 것으로 예상된다.
1 + 11 + 42 + 8 + 1 + 4 + 22 + 21 = 110
재귀적인 문제를 해결할 때에는 언제나 가장 간단한 문제를 해결하는 것 에 착수해야 한다.
그렇다면 여기서 제일 간단한 문제는 뭘까?
중첩되지 않은 리스트의 합을 구하는 문제 일 것이다.
위 함수는 프로그래밍 초보자도 이해할 수 있을 만큼 간단하다.
그렇다면 이 함수를 이용하여 원래 어려운 문제를 해결해 보자.
중첩된 리스트의 원소를 모두 더할 때 아주 자연스러운 생각은
- 중첩된 리스트의 어떤 원소가 리스트가 아니면 그냥 결과에 더한다.
- 원소가 리스트 이면 그 합을 결과에 더한다. 일 것이다.
따라서 다음과 같이 문제를 해결할 수 있다.
정말 간단하게 문제가 해결되었다.
간단한 문제의 해결법이 복잡한 문제의 해결법 인 것이다.
이를 for문이나 while문으로 해결할 수도 있겠지만 알다시피 중첩된 리스트가 몇 중으로 중첩되었는지를 모르기 때문에 매우 복잡한 결과가 되었을 것이다.
이로부터 몇 변의 단계가 걸릴지 예측하기 어려울 때 재귀를 고려하면 좋다는 일반적인 원리를 발견할 수 있다.
재귀가 어려워요
재귀가 어렵다고 말하는 사람 대부분과 이야기해 보면 공통된 답변을 찾을 수 있다.
그것은 바로 재귀가 일어나는 내부의 사실에 집중 하는것
재귀 함수가 호출 되었을 때 그 함수가 정확한 결과를 도출한다고 믿지 않고 정말 그런지 다시 머릿속으로 함수를 실행해보면서 마치 컴퓨터가 일하듯 알고리즘이 맞는지를 확인한다.
그러나 핵심은 재귀 함수가 호출될 때 올바른 결과를 도출한다 는 사실을 믿는 것 이다.
고등학교 때 수학적 귀납법을 떠올려 보자.
- n == 1 일 때 명제 F(1)이 성립한다.
- n == k 일 때 명제 F(k)이 성립하면 n=k+1 일 때도 F(k+1)이 성립한다.
- (1),(2)가 모두 참이라면 모든 자연수 n에 대해 F(n)은 성립한다.
이건 아마 대부분의 사람이 자연스럽게 받아들였을 것이다.
그렇다면
- 기본적인 문제 x에 대해서 함수 f(x)는 올바른 결과를 도출한다.
- 문제 P에 대해서 함수 f(P)의 결과가 올바르다면, P들로 구성된 문제 Q에 대해서 f(Q)의 결과가 올바르다.
- (1), (2)가 모두 참이라면 모든 문제 A에 대해 f(A)는 올바르다.
이거 받아들이 수 없는가?
대표적인 하노이의 탑 문제나 팩토리얼 문제를 이런식으로 보면 해결할 수 있다.
자연스러운 재귀
우리가 자주 사용하는 지수 의 경우에 수학적으로 다음과 같이 정의되어 있다
a^n의 경우,
- n == 0 이면 1
- n == p이면 a^p == a*a^(p-1)
이러한 정의를 우리는 자연스럽게 받아들이고 살아간다. 재귀적인 정의에 우리는 익숙해져 있는 것이다.
이로부터 재귀 문제에 익숙해져서 재귀 문제를 효율적으로 푸는 연습을 해보자.
참고 및 출처
https://blog.fupfin.com/?p=150