Recursive Functions

함수의 본문이 직접적으로든 간접적으로든 자기 자신을 다시 호출하는 경우 그 함수를 재귀 함수라고 부른다. 즉, 재귀 함수의 본문을 실행하는 과정에서 그 함수를 다시 적용해야 하는 상황이 발생할 수 있다. 파이썬에서 재귀 함수를 정의하기 위해 특별한 구문이 필요한 것은 아니지만, 이를 이해하고 작성하는 데는 약간의 노력이 필요하다.

우선 예제 문제부터 시작해보자. 자연수의 각 자릴수의 합을 구하는 함수를 작성해보자. 재귀 함수를 설계할 때는 문제를 더 단순한 문제로 나눌 수 있는 방법을 찾아야 한다. 이 경우, 연산자 % 와 // 를 사용하여 숫자를 두 부분으로 나눌 수 있다. "마지막 자릿수"와 "마지막 자릴 수를 제외한 나머지 숫자"들로

18117의 각 자릿수의 합은 1 + 8 + 1 + 1 + 7 = 18이다. 숫자를 분리했듯이, 이 합계 역시 마지막 자릴수인 7과 마지막 자릿수를 제외한 나머지 숫자의 합인 1 + 8 + 1 + 1 = 11로 나눌 수 있다. 이러한 분리는 우리에게 하나의 알고리즘을 제공한다. 숫자 n의 자릴수 합을 구하려면 마지막 자릿수인 n%10을 n//10의 자릿수 합에 더하면 된다. 여기에는 한가지 특수한 경우가 있다.

숫자가 한자리 뿐이라면, 그 자릿 수의 합은 숫자 자신과 같다. 이 알고리즘은 다음과 같이 재귀 함수로 구현될 수 있다.

이 sum_difits의 정의는 함수 본문 안에서 자기 자신을 호출하고 있음에도 불구하고 완전하고 정확하다. 숫자의 자릿수 합을 구하는 문제는 두 단계로 나뉜다. 마지막을 제외한 나머지 숫자의 자릿수 합을 구한 다음, 마지막 자릴수를 더하는 것이다. 이 2단계는 모두 원래 문제보다 더 단순하다. 첫번째 단계가 원해 문제와 똑같은 종류의 문제이기 때문에 이 함수는 재귀적이다. 즉, sum_digits를 구현하기 위해 정확히 우리에게 필요한 함수가 바로 sum_digits 자신인 셈이다.

우리는 환경 모델을 이용하여 이 재귀 함수가 어떻게 성공적으로 적용되는지 정확히 이해할 수 있다. 새로운 규칙은 필요하지 않다.

def문이 실행될 때 sum_digits라는 이름은 새로운 함수에 바인딩되지만, 함수의 본문은 아직 실행되지 않는다. 따라서 sum_digits의 순환적인 구조는 아직 문제가 되지 않는다. 그다음 sum_digits(738)이 호출된다.

n이 738에 바인딩된 sum_digits의 로컬 프레임이 생성되고, 그 프레임으로 시작하는 환경에서 본문이 실행된다.
738은 10보다 작지 않으므로 4행의 할당문이 실행되어 738을 73과 8로 나눈다.
이어지는 return문에서, 현재 환경의 all_but_last 값인 73에 대해 sum_digits가 호출된다.
sum_digits를 위한 또 다른 로컬 프레임이 생성되며 이번에는 n이 73에 바인딩된다. 이 프레임으로 시작하는 새환경에서 본문이 다시 실행된다.
73역시 10보다 작지 않으므로 7과 3으로 나뉘고, 이 프레임에서 평가된 all_but_last값인 7에 대해 sum_digits가 호출된다.
n이 7에 바인딩 된 세번째 로컬 프레임이 생성된다.
이 프레임으로 시작하는 환경에서는 n < 10이 참이 되므로, 7이 반환된다.
두번째 로컬 프레임에서 이 반환값 7은 last의 값인 3과 더해져 10을 반환한다.
첫번째 로컬 프레임에서 이 반환값 10은 last의 값인 8과 더해져 18을 반환한다.

이 재귀함수는 순환적인 특성에도 불구하고 정확하게 적용된다. 왜냐하면 함수가 두 번 적용되었지만, 매번 서로 다른 인자를 가지고 적용되었기 때문이다.

게다가 두번째 적용은 첫번째보다 더 단순한 인스턴스의 문제였다. sum_digits(18117)호출에 대한 환경 다이어그램을 그려보면, 결국 한자리 숫자에 도달할 때까지 매번 이어지는 호출이 이전보다 더 작은 인자를 받는다는 것을 알 수 있다.

이 예제는 또한 본문이 단순한 함수가 재귀를 사용하여 어떻게 복잡한 계산 과정을 만들어낼 수 있는지 잘 보여준다.

The Anatomy of Recursive Functions

많은 재귀 함수의 본문에서는 공통된 패턴을 찾을 수 있다 본문은 기본 케이스로 시작하는데, 이는 가장 처리하기 단순한 입력에 대한 함수의 동작을 정의하는 조건문이다. sum_digits의 경우, 기본 케이스는 모든 한 자리 수 인자이며, 이때는 단순히 그 인자를 반환한다. 어떤 재귀 함수들은 여러 개의 기본 케이스를 갖기도 한다.

기본 케이스 뒤에는 하나 이상의 재귀 호출이 따른다. 재귀 호출은 항상 특정한 성질을 갖는데, 바로 원래의 문제를 단순화한다는 것이다. 재귀 함수는 문제를 점진적으로 단순화함으로써 계산을 표현한다.

예를 들어, 7의 자릿수 합을 구하는 것은 73의 자릿수 합을 구하는 것보다 단순하며, 이는 다시 738의 자릿수 합을 구하는 것보다 단순하다. 각각의 후속 호출에서 수행해야 할 작업은 점점 줄어든다.

재귀 함수는 종종 우리가 이전에 사용했던 반복적 접근 방식과는 다른 방식으로 문제를 해결한다. n팩토리얼을 계산하는 함수 fact를 예로 들어보자. 예를 들어 fact(4)는 4! = 4 * 3* 2* 1 = 24를 계산한다.

while 문을 사용한 자연스러운 구현은 n까지의 각 양의 정수를 차례로 곱하여 합계는 누적한다.

반면 팩토리얼의 재귀적 구현은 fact(n)을 더 단순한 문제인 fact(n-1)의 관점에서 표현할 수 있다. 재귀의 기본 케이스는 문제의 가장 단순한 형태인 fact(1) = 1이다

이 두 팩토리얼 함수는 개념적으로 다르다. 반복 함수는 기본 케이스인 1부터 시작하여 각 항을 차례로 곱해나가며 최종 합계를 구축한다. 반면, 재귀 함수는 최종 항인 n과 더 단순한 문제의 결과인 fact(n-1)로 부터 결과를 직접 구축한다.

재귀가 점점 더 단순한 문제 인스턴스에 fact 함수를 적용하며 풀려나감에 따라, 결과는 결국 기본 케이스에서 시작하여 만들어진다. 재귀는 fact에 인자 1을전달하면서 끝나며, 각 호출의 결과는 기본 케이스에 도달할 때까지 다음 호출에 의존하게 된다.

이 재귀 함수의 정확성은 팩토리얼에 대한 표준 수학적 정의로부터 쉽게 검증할 수 있다.

n! = n * (n-1)!

(n-1)! = (n-1) * (n-2) * ... * 1

우리의 계산 모델을 사용하여 재귀를 풀어볼 수도 있지만, 재귀 호출을 하나의 함수적 추상화로 생각하는 것이 훨씬 명확할때가 많다. 즉, 우리는 fact 본문 내에서 fact(n-1)이 어떻게 구현되었는지 신경쓰지 않아야 하며, 단순히 그것이 n-1의 팩토리얼을 계산할 것이라고 믿어야 한다.

재귀 호출을 함수적 추상화로 취급하는 것을 재귀적 믿음의 도약이라고 부른다. 함수를 자기자신을 이용해 정의하지만, 함수의 정확성을 검증할 때 더 단순한 케이스들이 올바르게 작동할 것이라고 단순히 믿는 것이다. 이예제에서 우리는 fact(n-1)이 (n-1)!을 정확히 계산할 것이라고 믿고, 이 가정이 성립할 때 n!이 올바르게 계산되는지만 확인하면 된다. 이런 방식에서 재귀 함수의 정확성을 검증하는 것은 귀납법을 통한 증명의 한 형태이다.

fact_iter과 fact는 또한 전자가 재귀 구현에서 필요 없는 total과 k라는 2개의 추가 이름을 도입해야 한다는 점에서도 다르다. 일반적으로 반복 함수는 계산 과정 내내 변화하는 로컬 상태를 유지해야 한다. 반복의 어느 시점에서든 그 상태는 완료된 작업의 결과와 남은 작업의 양을 특정짓는다. 예를 들어 k가 3이고 total이 2일때 아직 처리해야 할 항이 3과 4로 두개 남아있다. 반면, fact는 단일인자 n에 의해 특정지어진다. 계산의 상태는 환경의 구조 내에 완전히 포함되어 있으며, 환경의 반환 값들이 tatal의 역할을 대신하고, k를 명시적으로 추적하는 대신 서로 다른 프레임에서 n을 서로 다른 값에 바인딩한다.

재귀 함수는 호출 표현식을 평가하는 규칙을 활용하여, 이름에 값을 바인딩하므로 반복 중에 로컬 이름을 정확히 할당해야 하는 번거로움을 피할 수 있는 경우가 많다. 이러한 이유로 재귀 함수는 올바르게 정의하기가 더 쉬울 수 있다.

Mutal Recursion

재귀 절차가 서로를 호출하는 두 함수로 나뉘어 있을 때, 이 함수들은 상호 재귀 관계에 있다고 한다. 예시로 비음수 정수에 대한 짝수와 홀수의 다음 정의를 고려해보자.

어떤 수가 짝수라면, 그 수는 홀수보다 1 큰 수이다.
어떤 수가 홀수라면, 그 수는 짝수보다 1 큰 수이다.
0은 짝수이다.

이 정의를 사용하여 어떤 수가 짝수인지 홀수인지 판별하는 상호 재귀 함수를 구현할 수 있다.

상호 재귀 함수는 두 함수 사이의 추상화 경계를 허물어 하나의 재귀 함수로 바꿀 수 있다. 이 예제에서는 is_odd의 본물을 is_even 안으로 병합할 수 있는데, 이때 is_odd로 전달되었던 인자를 반영하여 본문 내의 n을 n-1로 교체해야 한다.

이와 같이 상호 재귀는 단순 재귀보다 더 신비롭거나 강력한 것이 아니며, 복잡한 재귀 프로그램 내에서 추상화를 유지하기 위한 매커니즘을 제공할 뿐이다.

Printing in Recursive Functions

재귀 함수에 의해 전개되는 계산 과정은 print 호출을 사용하여 시각화할 수 있는 경우가 많다. 예시로 숫자의 접두어를 가장 큰 것부터 가장 작은 것까지, 그리고 다시 가장 큰 것까지 출력하는 cascade 함수를 구현해보자.

이 재귀 함수에서 기본 케이스는 한 자리 숫자이며, 이때는 그 숫자를 출력한다. 그 이외의 경우, 재귀 호출은 2개의 print 호출 사이에 위치한다.

기본 케이스를 반드시 재귀 호출 앞에 명시해야 한다는 엄격한 규칙이 있는 것은 아니다. 사실 이 함수는 print(n)이 조건문의 두 절 모두에서 반복된다는 점을 관찰함으로써 더 간결하게 표현할 수 있으며 따라서, 조건문 앞에 배치할 수 있다.

상호 재귀의 또 다른 예로, 탁자 위에 n개의 조약돌이 놓여있는 2인용 게임을 생각해보자. 플레이어들은 번갈아 가며 탁자에서 하나 또는 두 개의 조약돌을 제거하며, 마지막 조약돌을 제거하는 플레이어가 승리한다. 앨리스와 밥이 이 게임을 하며 각각 다음과 같은 단순한 전략을 사용한다고 가정해보자.

앨리스 : 항상 조약돌 하나를 제거함
밥 : 탁자에 놓인 조약돌이 짝수 개이면 두개를 제거하고, 그렇지 않으면 하나를 제거함

초기 조약돌 개수 n이 주어지고 앨리스가 먼저 시작할 때 누가 게임에서 이길까?

이 문제의 자연스러운 분해 방법은 각 전략을 고유한 함수 안에 캡슐화하는 것이다. 이렇게 하면 다른 전략에 영향을 주지 않고 한 전략을 수정할 수 있어, 두 전략 사이의 추상화 방법을 유지할 수 있다. 게임의 턴제 특성을 반영하기 위해, 이 두 함수는 각 턴이 끝날 때 서로를 호출한다.

play_bob에서 우리는 하나의 함수 본문 안에 여러개의 재귀 호출이 나타날 수 있음을 확인했다. 하지만 이 예제에서 play_bob의 호출은 play_alice를 최대 한번만 호출한다. 다음 섹션에서는 단일 함수 호출이 여러개의 직접적인 재귀 호출을 수행할 때 어떤 일이 발생하는지 살펴보자.

Tree Recursion

또 다른 공통적인 계산 패턴은 tree recursion이라 불리며, 이는 함수가 자기 자신을 한 번 이상 호출하는 구조를 말한다. 예시로, 앞의 두 숫자를 더해 다음 숫자를 만드는 피보나치 수열 계산을 생각해보자.

이 재귀적 정의는 이전의 시도들에 비해 굉장히 매력적이다. 우리가 익히 알고 있는 피보나치 수열의 정의를 그대로 거울처럼 반영하고 있기 때문이다. 여러 개의 재귀 호출을 하는 함수를 트리 재귀라고 부른 이유는, 각 호출이 여러개의 더 작은 호출로 가지를 치고, 그 호출들이 다시 더 작은 호출들로 뻗어 나가기 때문이다. 이는 마치 나무의 가지가 줄기에서 뻗어 나갈수록 크기는 작아지지만, 그 수는 많아지는 모습과 같다.

Example : Partitons

양의 정수 n을 최대 크기 m 이하의 인자들로 나누는 partitions의 수는 n을 m이하의 양의 정수들의 합으로 나타낼 수 있는 방법의 가짓수를 의미한다. 예를 들어 최대 크기 4 이하의 인자들을 사용하여 6을 분할하는 방법은 총 9가지이다.

6 = 2 + 4
6 = 1 + 1 + 4
6 = 3 + 3
6 = 1 + 2 + 3
6 = 1 + 1 + 1 + 3
6 = 2 + 2 + 2
6 = 1 + 1 + 2 + 2
6 = 1 + 1 + 1 + 1 + 2
6 = 1 + 1 + 1 + 1 + 1 + 1

우리는 최대 m까지의 인자를 사용하여 n을 분할하는 서로 다른 방법의 수를 반환하는 count_partitions(n, m) 함수를 정의할 것이다. 이 함수는 다음과 같은 관찰을 바탕으로 트리 재귀 함수를 통해 간단히 해결할 수 있다.

m 이하의 정수를 사용하여 n을 분할하는 방법의 수는 다음 두 가지의 합과 같다.

m 이하의 정수를 사용하여 n - m을 분할하는 방법의 수
m - 1 이하의 정수를 사용하여 n을 분할하는 방법의 수

이것이 왜 사실인지 이해하기 위해 n을 분할하는 모든 방법이 다음 두 그룹으로 나뉜다는 점을 주목해야 한다. m을 적어도 하나 포함하는 그룹과 그렇지 않은 그룹, 또한 첫 번째 그룹의 각 분할은 n - m 분할 뒤에 마지막으로 m을 덧붙인 것과 같다. 위의 예시에서 처음 2개의 분할은 4를 포함하고 있으며, 나머지는 그렇지 않다.

따라서 우리는 m 이하의 정수를 사용하여 n을 분할하는 문제를 두가지 더 단순한 문제로 재귀적으로 줄일 수 있다.

더 작은 수인 n - m을 분할하는 문제,
더 작은 구성 요소인 m - 1까지를 사용하여 분할하는 문제

구현을 완성하기 위해 다음과 같은 기본케이스를 지정해야 한다.

0을 분할하는 방법은 1가지이다.
음수 n을 분할하는 방법은 0가지이다.
0보다 큰 n을 0이하의 크기를 가진 인자로 분할하는 방법은 0가지이다.

우리는 트리 재귀 함수를 다양한 가능성을 탐색하는 과정으로 생각할 수 있다. 이 경우, 우리는 크기 m인 인자를 사용할 가능성과 사용하지 않을 가능성을 탐색한다. 첫 번째와 두 번째 재귀 호출은 각각 이러한 가능성들에 대응한다.

이 함수를 재귀 없이 구현하는 것은 상당히 더 복잡할 것이다.