Python의 재귀 곱하기

Python에서는 * 연산자로 정수를 곱할 수 있지만, 곱셈을 재귀로 구현하면 문제를 더 작은 문제로 줄여 가는 방식을 이해하는 데 도움이 됩니다. 아래 예제에서는 반복 덧셈, 절반씩 줄이는 방법, 누산기를 사용하는 변형을 살펴봅니다. 이 예제는 학습용이므로 일반적인 애플리케이션 코드에서는 내장 연산자를 사용하세요.

재귀 이해하기

재귀 함수는 더 작은 입력으로 자기 자신을 호출해 문제를 해결합니다. 다시 호출하지 않고 결과를 반환하는 기본 사례와, 그 기본 사례에 가까워지도록 진행하는 재귀 사례가 필요합니다. 각 호출은 하위 호출이 결과를 반환할 때까지 기다립니다. 그런 다음 호출이 되돌아오면서 각 단계에 남아 있던 연산을 마칩니다.

반복 덧셈으로 곱셈을 구현할 때는 재귀 사례에서 곱하는 수를 1씩 줄이고, 반환된 결과에 피승수를 더합니다. 곱하는 수가 0이 되면 기본 사례에 도달합니다. 호출이 언젠가 멈추도록 하는 조건이 없으면 함수는 결과를 반환할 수 없습니다.

기본 재귀 곱셈

가장 간단한 방법은 호출할 때마다 두 번째 입력을 1씩 줄인 다음, 호출이 되돌아오는 동안 첫 번째 입력을 더하는 것입니다.

아래 예제를 실행해 보세요.

이 섹션의 코드와 표시되는 레이블 또는 출력은 영어로 유지됩니다.

def recursive_multiply(a, b):
    if b == 0:
        return 0
    if b < 0:
        return recursive_multiply(-a, -b)
    return a + recursive_multiply(a, b - 1)

print(recursive_multiply(5, 3))

이 함수는 b가 양수인 동안 각 단계에서 a를 한 번씩 더합니다. b가 음수이면 두 피연산자의 부호를 모두 바꿔 양수를 세는 동일한 재귀 방식을 적용할 수 있으며, 곱의 값은 그대로 유지됩니다. 이 방법은 피승수가 음수인 경우도 처리합니다.

각 호출은 b가 기본 사례에 도달할 때까지 값을 1씩 줄입니다. 그런 다음 호출이 역순으로 반환되면서 각 단계에서 a를 더합니다. 재귀 과정을 따라가기는 쉽지만, 호출 횟수는 곱하는 수의 절댓값에 비례합니다. 따라서 곱하는 수가 크면 Python의 재귀 깊이 제한을 초과할 수 있습니다. 코드와 출력 블록은 예제의 레이블을 포함해 그대로 유지되므로, 출력 레이블은 영어로 표시됩니다.

음수 정수와 0 처리

같은 함수로 0과 모든 부호 조합을 처리할 수 있습니다. 곱하는 수가 0이면 즉시 0을 반환합니다. 곱하는 수가 음수라면 두 피연산자의 부호를 모두 바꾸어 양수인 경우로 계산할 수 있고, 수학적인 곱은 변하지 않습니다.

이 섹션의 코드와 표시되는 레이블 또는 출력은 영어로 유지됩니다.

def recursive_multiply(a, b):
    if b == 0:
        return 0
    if b < 0:
        return recursive_multiply(-a, -b)
    return a + recursive_multiply(a, b - 1)

for pair in ((5, 3), (-5, 3), (5, -3), (-5, -3), (5, 0)):
    print(pair, recursive_multiply(*pair))

네 가지 부호 조합의 결과는 일반적인 부호 규칙을 따릅니다. 두 피연산자의 부호가 같으면 양수, 다르면 음수가 됩니다. 피연산자 중 하나가 0이면 결과도 0입니다. 반복문은 각 입력 쌍과 곱을 함께 출력하므로 부호에 따른 결과를 쉽게 비교할 수 있습니다. 이 출력 블록의 레이블은 코드와의 바이트 동일성을 위해 영어로 유지됩니다.

절반씩 줄여 재귀 호출 줄이기

곱하는 수를 절반으로 줄일 수 있다면 매번 1씩 빼지 않아도 됩니다. 양수 b에 대해 half를 a와 b // 2의 곱이라고 합시다. b가 짝수이면 전체 결과는 half + half이고, 홀수이면 여기에 a를 한 번 더해야 합니다. 정수 나눗셈과 나머지 검사를 사용하면 비트 연산 없이 이 재귀식을 표현할 수 있습니다.

이 섹션의 코드와 표시되는 레이블 또는 출력은 영어로 유지됩니다.

def multiply_by_halving(a, b):
    if b == 0:
        return 0
    if b < 0:
        return multiply_by_halving(-a, -b)
    half = multiply_by_halving(a, b // 2)
    if b % 2 == 0:
        return half + half
    return half + half + a

print(multiply_by_halving(5, 3))

각 재귀 단계에서 곱하는 수가 대략 절반으로 줄어들기 때문에, 호출 깊이는 그 수의 크기 자체가 아니라 몇 번 절반으로 나눌 수 있는지에 비례해 증가합니다. 이 방법도 덧셈을 수행하고 Python의 호출 스택을 사용합니다. 재귀식을 줄여 가는 방법을 보여 주는 데는 유용하지만, 일반적인 코드에서는 내장 곱셈이 더 간단합니다.

Python의 꼬리 재귀

꼬리 재귀 함수에서는 재귀 호출이 마지막 연산이며, 누산기에 호출 과정의 결과를 누적합니다. 이렇게 하면 남은 작업이 기록되는 위치는 달라지지만, Python은 하나의 스택 프레임을 재사용하도록 꼬리 호출을 최적화하지 않습니다. 따라서 호출 스택의 한계는 여전히 적용됩니다.

이 섹션의 코드와 표시되는 레이블 또는 출력은 영어로 유지됩니다.

def tail_recursive_multiply(a, b, accumulator=0):
    if b == 0:
        return accumulator
    if b < 0:
        return tail_recursive_multiply(-a, -b, accumulator)
    return tail_recursive_multiply(a, b - 1, accumulator + a)

print(tail_recursive_multiply(5, 3))

누산기는 0에서 시작해 양수 단계마다 a를 하나씩 더합니다. 곱하는 수가 0에 도달하면 누산기에 곱의 결과가 담겨 있습니다. 반복 덧셈과 마찬가지로 이 방법도 곱하는 수의 크기에 비례하는 횟수만큼 호출하므로, 꼬리 호출 방식이라고 해서 Python에서 큰 입력을 안전하게 처리할 수 있는 것은 아닙니다.

재귀 곱셈이 유용한 경우

이 구현들을 살펴보면 기본 사례와 재귀적 진행 방식, 그리고 선형 호출 깊이와 로그 호출 깊이의 차이를 이해할 수 있습니다. 반복 덧셈 방식과 꼬리 재귀 방식의 깊이는 선형이고, 절반씩 줄이는 방식의 깊이는 로그 수준입니다. 세 방법 모두 함수 호출과 스택에 따른 비용이 들며, Python은 환경에 따라 일정한 재귀 깊이 한도를 보장하지 않습니다.

실제 정수 연산에는 a * b를 사용하는 편이 좋습니다. 더 명확하고 Python 수준의 재귀 호출을 추가로 만들지 않기 때문입니다. 재귀를 공부하거나 문제에서 재귀 방식이 특별히 요구될 때 재귀 곱셈을 사용하고, 선택한 재귀식에 맞게 입력을 충분히 작게 유지하세요.