재귀 함수의 이해와 정리
프로그래밍 설계 원리의 자연스러운 터득, 첫 번째 재귀 함수
코딩을 하면서, 몰입감에 빠져 흥미를 느낀 적은 드물었다. 하지만 어떠한 간단한 문제라도 내가 직접 코딩해서 맞춘 성공 사례가 쌓이다가, 이제는 코딩 과정을 계속 반추하면서 끝끝내 직접 수학 알고리즘을 함수로 정확하게 구현해내자 쏠쏠한 성취감이 느껴졌다.
일전에 공공기관에서 만난 한 웹 개발자 형은 용역업체의 직원이라서 매일 하는 업무 중 하나가 갑의 위치인 공무원이 말하는 것을 그대로 타이핑하거나, 민원 수준의 전화를 응대하는 거였다. 잠깐 알고 지냈던 그 개발자 형은 대기업의 하청 개발 프로젝트의 프리랜서로 일하기 위해 곧 떠났다.
개발이라고 처음부터 무에서 유를 창조하는 일(세상 어디에도 이런 일을 하는 직업은 일론 머스크의 화성에 인류 주거지 건설 외에는 없다.)을 하는 것이 아니라는 것은 그때 알았다. 하지만, 그 형과 몇 번 나눴던 대화 중에 자신은 어릴 때부터 수학 문제 푸는 것을 굉장히 좋아했다는 것을 들었다. 수학을 아주 잘했던 것은 아니지만 뭔가 규칙성을 발견하고 답을 찾아나가는 과정이 아주 흥미로웠다고 한 기억이 난다. '재귀와 반복:자연수 계산'이라는 챕터를 실습하면서 스스로 과정을 적어(혹은 디버깅) 가면서 발견한 규칙성을 통해 어떻게 코드(재귀 함수)가 구현되는지 아는 재미가 바로 그 형이 말했던 바와 같다고 느꼈다.
고등학교 때 얼마간이라도 '수학의 정석'이나 교과서를 붙잡고 식을 세우고 정리하고 문제를 푼 경험이 그나마 지금 와서야 도움이 될 수가 있어서 다행이다. 배운 게 아무 효용가치가 없다면(사실, 학교에서 배운 수학에서 미분, 적분 말고는 사회에서 도움받을만한 개념이 있을까 싶었지만 '지수와 로그' 그리고 '수와 식'이 프로그래밍에서 도움이 될 줄야!), 학교는 사회적 지능의 퇴화를 막기 위해 가는 그 이상, 그 이하의 물리적 공간도 아녔다고 생각했었을 수도 있겠다.
프로그래밍에서의 함수는 엄밀히 말하면 수학에서의 함수와 다르다. 수학에서의 함수는 만약, f(x) = 2x+1라는 함수에서 x 값에 어떠한 상수가 들어가면 f(x)의 계산 값이 y의 값으로 치환된다. 하지만 프로그래밍에서는 f(x)에 특정값이 들어가서 어떤 결괏값을 반환해주는지는 함수 내부의 구조를 들여다보지 않고는 알 수 없다. 즉 어떤 '함(보자기)'과 같이 그 안에 '어떠한 조건'과 절차가 있는지는 모르지만, 함을 들어갔다 나오면 처음의 입력값과 다른 출력 값을 뱉어낼 수 있다. 특히 재귀 함수 같은 경우는 특정 함수에 동일한 함수가 통째로 들어가는('재귀') 구조이기 때문에 흥미로웠다. 마치 러시아 인형과 같이 인형 안에 그와 똑같은 인형이 크기만 작아 진채 계속 되풀이되는 구조처럼 말이다.
그런데 앞선 섹션에서 언급한 sigma(n + 1) = sigma(n) + n+1이라는 재귀식에서 sigma(n)까지의 합은 계산했다는 가정하(귀납)에 n+1까지의 합만 더하면 sigma(n+1) 은 구할 수 있다는 발상은 금융에서의 담보를 떠올리게 하기도 한다. 신용카드나 대출부터 더 나아가 주식시장에서의 '선물*' 옵션까지 금융권에서 이 재귀라는 개념은 안 쓰이는 데가 없다는 것을 깨달았다. 예를 들면 일론 머스크가 이번에 트위터를 인수하기 위해 은행으로부터 약 240억 달러를 대출받는 조건으로 그의 회사 테슬라의 지분 일부를 담보로 걸었다는 기사에서, 그가 이미 240억 달러의 대출금을 갚아줄 수 있다(담보로라도 갚아줄 수 있다)는 가정 하에 은행은 그에게 돈을 빌려준 것이다.
단순히 sigma(n + 1)까지의 합을 어떻게 계산할지를 궁리하면서 sigma(n)은 이미 n까지의 합을 구했다는 가정을 발상해낸 '함수'적인 로직은 정말 대단하다는 것인데, 필자가 되뇌는 말이 무슨 말인지 이해가 되시려는 독자 분이 있으실까 궁금하다.
재귀 함수 파트를 여러 가지 수학적 증명을 빌려와서 공부하면서 깨달은 것은 재귀 함수를 알기 위해서는 수학에서의 '항등원'과 '곱셈 공식'의 개념을 어렴풋이 기억한다면 이 재귀 함수의 원리를 쉽게 터득할 수 있다는 것이다.
곱셈 연산자가 없더라도 덧셈과 뺄셈 연산자만 가지고도 곱셈을 할 수 있는 알고리즘을 구현하는 것을 통해 재귀 함수의 예를 한 번 더 들어보겠다. 2 곱하기 2는 결국 2를 2번 더한다는 의미와 같기 때문에 곱셈이 없어도 덧셈과 뺄셈만으로도 곱셈과 같은 결괏값을 내놓을 수 있다. 그래서 다음과 같은 재귀로 곱셈(multiply) 함수를 구현할 수 있다.
재귀 함수의 반복 조건인 n > 0 일 때,
m × n = m + m × (n － 1)
재귀 함수의 종료 조건인 n = 0 일 때,
0
위의 재귀식에서 중간에 곱셈이 있는데 왜 곱셈이 없는 곱셈 재귀 함수냐고 반문할 수 있다. m 곱하기 n은 m을 n번 더하는 것과 같다는 원리를 통해서 이 재귀 함수는 덧셈하는 횟수가 1씩 줄어드는 n에 비례한다는 것을 알 수 있고, 이것은 식에서의 곱셈 연산자가 실제로는 함수를 호출하는 횟수(=덧셈의 횟수)라는 것을 알 수 있다. 즉 함수의 함수(재귀)인 셈이다.
곱셈 없는 곱셈 재귀함수 구현
def mult(m, n):
if n > 0:
return m + mult(m, n-1)
else: # n == 0
return 0
# Test code
print(mult(3,6)) # 18
print(mult(0,6)) # 0
print(mult(3,0)) # 0
print(mult(0,0)) # 0
위의 재귀 함수에서 곱하는 수 파라미터(형식 인자)의 m과 n에서 n의 값(인수)이 0보다 크면 반환 값이 'm + mult(m, n-1)'이다. 즉 이 재귀 함수 mult(m, n)에 mult(m, n값 1씩 감소)를 다시 그대로 넣은 후 m을 더해주기를 기다리는 상태(로컬 함수 외부의 기억 공간 차지)를 내어 놓는다.
그리고 n의 값(인수)이 0과 같게 되면, 0을 반환한다. 이 함수의 호출을 실행한 예를 추적한 것이 아래와 같다.
mult(m, n)이 mult(3, 6) 일 때 함수 실행 추적
=> 3 + mult(3, 5) ←위의 함수 mult(3, 6)이 반복 조건(n>0)을 만족하므로 mult(3, 5) 반환)
=> 3 + 3 + mult(3, 4)
=> 3 + 3 + 3 + mult(3, 3)
=> 3 + 3 + 3 + 3 + mult(3, 2)
=> 3 + 3 + 3 + 3 + 3 + mult(3, 1)
=> 3 + 3 + 3 + 3 + 3 + 3 + mult(3, 0)
=> 3 + 3 + 3 + 3 + 3 + 3 + 0 ←(위의 함수 결괏값 mult(3,0)이 종료 조건을 만족하므로 0을 반환)
=> 3 + 3 + 3 + 3 + 3 + 3 (이후 이 재귀 함수 외부에 계속 누적되고 있었던 식의 계산이 이루어짐.)
=> 3 + 3 + 3 + 3 + 6
=> 3 + 3 + 3 + 9
=> 3 + 3 + 12
=> 3 + 15
=> 18 (출력 값)
여기서 종료 조건을 n == 0 일 때, 1이 아니라 0으로 결괏값(인수)을 던져주는 이유가 함수의 함수가 곱셉이 아니라 덧셈이기 때문이라는 것을 알 수 있다. 즉 이 함수는 곱셈을 사용하지 않고 곱셈을 실행하는 알고리즘이기 때문에 아직 계산하지 않고 대기하고 있는 3들의 덧셈이 이루어지고난 다음 결괏값을 반환한다. 이때 0은 뎃셈의 항등원(identity element)이라고 하는데, 0을 어떤 수에 더해도 그 수는 변하지 않기 때문에, 종료 조건을 만족할 때 기존 식의 값에 영향을 주지 않는 0을 반환한다.
함수의 계산비용에서 시간을 줄일 수 있는 '나눠 풀기’ 재귀 함수(fast multiply)를 다음과 같은 재귀로 구현할 수 있다.
재귀 함수의 반복 조건인 n > 0이며 짝수일 때,
m × n = (m + m) × (n ÷ 2) **
재귀 함수의 반복 조건인 n > 0이며 홀수일 때(기존의 덧셈/뺄셈 알고리즘),
m × n = m + m × (n － 1)
재귀 함수의 종료 조건인 n = 0 일 때,
0
곱셈 없는 빠른 곱셈 재귀함수 구현
def fastmult(m, n):
if n > 0: # 반복 조건
if n % 2 == 0: # 짝수일 경우
return fastmult(2*m, n//2)
else: # 홀수일 경우
return m + fastmult(m, n-1)
else: # 종료 조건
return 0
위의 재귀 함수는 분할 정복(divide-and-conquer) 방법을 통해서 문제 해결 대상을 반으로 나눠(짝수/홀수) 각각 따로 푼 다음, 합치는 방안으로 반복 조건 중 n이 짝수일 경우 fastmult(2*m, n//2)를 반환한다. 이 함수의 인수 전달은 n이 짝수일 때는 m을 더하는 대신 m을 두 번 곱한 값(=m+m)을 m에 저장하고, n을 2로 나누는 계산을 통해 기존의 덧셈/뺄셈 알고리즘의 함수 호출 횟수를 절반 가량(시간 '***최적화', 시간 단위 계산비용 분석) 줄인다. 재귀 함수 fastmult(3,6) 호출을 실행 추적하면 다음과 같다.
fastmult(3,6)
=> fastmult(6,3)
=> 6 + fastmult(6,2)
=> 6 + fastmult(12,1)
=> 6 + 12 + fastmult(12,0)
=> 6 + 12 + 0
=> 6 + 12
=> 18
mult(3, 6) 때의 덧셈 횟수가 6회였는데, 단 2회로 삼분의 일이 줄었다. 계산 비용 분석에서 시간은 덧셈하는 횟수에 비례하므로 시간이 절반 이상 주는 것이 분할 정복 방법을 이용한 재귀 함수다. 이때 덧셈을 하는 횟수가 log2(밑수) n에 비례한다는 것을 알 수 있다.
재귀 함수의 계산비용 분석에서 필요한 지수로그 법칙. 언급한 곱셉의 성질을 이용하여 덧셈 횟수가 log2(밑수) n에 비례한다.정리
재귀 함수는 같은 수식의 함수를 종료 조건을 만족할 때까지 반복시키는 구조의 함수다(즉, 아래의 '꼬리 재귀 함수'로 변환 시에 카운터(n)와 누적기(sum) 역할을 하는 변수가 재귀의 구조를 반복하게 하는 조건이다). 아래는 위의 '덧셈/뺄셈/절반 알고리즘'을 꼬리 재귀 함수(함수 내부에 전용 재귀함수를 포함하고 있는 함수)로 바꾼 것이다. 여기서 횟수를 세는(카운터) 역할을 하는 파라미터(형식 인자) n과 반환 값을 계속 누적시키는 누적기 역할을 하는 파라미터 변수 sum을 볼 수 있다.
def fastmult(m, n):
def loop(m, n, sum):
if n > 0: # 반복 조건
if n % 2 == 0: # 짝수일 경우
return loop(2*m, n//2, sum)
else: # 홀수일 경우
return loop(m, n-1, sum+m)
else: # 종료 조건
return sum
return loop(m, n, 0)
위의 loop라는 전용 재귀함수에서 n이 카운터(함수 호출 횟수) 역할을 하고, sum이 누적기(계산 반환값 누적) 역할을 한다. 반복 조건 분기 중 짝수일 경우에는 함수 호출 횟수를 줄이기 위해 n값을 절반으로 나눠서 함수 덧셈 횟수(인수의 크기에 비례)를 절반 가량 줄이는 대신, 계산값(m)을 두 배 한다(절반 나누고 두배 곱하니 결괏값이 동일함). loop 함수에서 조건 분기 중 홀수일 경우에는 카운터(함수 호출 횟수)를 하나 줄임과 동시에 기존의 계산 값에 결괏값을 누적한다(sum+m). 마지막으로 종료 조건(n==0)을 만족하면 지금까지 누적된 sum의 합산을 재귀함수의 최종값으로 돌려준다.
*선물 : 장래의 일정한 시기에 상품을 넘겨준다는 조건으로 현재 시점에서 가격을 정해 매매 계약을 하는 거래를 선물 거래라 한다. 보통 선물 거래는 주식이 유명하지만 사실 선물 방식으로 거래되는 상품은 석유, 농산물, 주식, 외환 등 매우 다양하다(발췌: namuwiki).
**절반 알고리즘(n이 짝수일 경우) 증명
m × n = (m + m) × (n ÷ 2)
= m × (n ÷ 2) + m × (n ÷ 2)
m × n m × n
= ---------- + -----------
2 2
2(m × n)
= --------------
2
= m × n
***최적화(재귀 함수의 계산비용 분석) : 시간 단위로는 프로그램이 얼마나 빨리 답을 계산하는지 따지고, 공간 단위로는 답을 계산하면서 얼마나 많은 공간(힙 메모리)을 사용하는지 따진다. 변수 저장 시에 로컬 변수는 스택이라는 메모리에 저장하는데 반면, 외부(전역) 변수는 힙이라는 메모리에 저장한다. 중요한 건, 스택에 저장된 변수는 사용하지 않으면 컴퓨터가 알아서 제거하는데 반해, 힙에 저장되었던 내용은 사용자가 따로 제거하지 않으면 계속 남아 있다. 자바에서는 이를 찌꺼기 수거(garbage collection)라고 불리는 기능이 이것도 제거해주지만, C나 C++ 등의 언어는 이것을 명령어를 통해 사용자가 직접 제거해줘야 메모리의 불필요한 낭비를 막을 수 있다. (스택(Stack)과 힙(Heap) 차이점 – JungHyun Baek – Developer from South Korea (junghyun100.github.io)
참조
1) 도경구 (2021). 제어 구조의 설계 원리를 중심으로 배우는 프로그래밍의 정석 파이썬.
