재귀 알고리즘: 거울에 비춰진 거울 속의 거울 속의 거울 속의 ~

재귀란?

어떤 이벤트에서 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의하는 경우를 재귀(recursion)라고 합니다. 어떤 사건의 결과가 동일한 사건의 원인이 되는 경우를 재귀라고 합니다. 자연수의 정의를 예로 들어보겠습니다. 자연수를 1,2,3,4,...,의 규칙성을 가진 수라고 정의할 수 있습니다. 이를 재귀적 형태로 정의하면 다음과 같습니다.

1은 자연수다.
자연수의 다음 수는 자연수다.

팩토리얼 알아보기

팩토리얼 문제 또한 재귀알고리즘을 통해 해결할 수 있습니다. 정수 n의 팩토리얼은 다음과 같이 재귀적 정의를 할 수 있습니다.

n 이 자연수일 때,
    n = 0 이면, 0! = 1
    n > 0 이면, n! = n * (n-1)!

이를 함수로 구현하면 다음과 같습니다.

def factorial(n: int): -> int
    if n == 0:
        return 1
    if n > 0:
        return n * factorial(n-1)

재귀 호출

factorial 함수를 호출 할 경우 factorial 함수 내부에서 자신과 동일한 함수를 호출합니다. 이러한 호출방식을 재귀호출이라고 합니다. 재귀호출은 ‘자기자신’이 아닌, ‘자기자신과 똑같은 함수’를 호출한다고 이해하는 것이 자연스럽습니다.

재귀호출방식으로 직접재귀와 간접재귀가 있습니다. 직접재귀는 자기자신과 동일한 함수를 호출하는 방식입니다. 간접재귀는 a()함수가 b()함수를 호출하고 b()함수가 내부적으로 다시 a()함수를 호출하는 방식입니다.

유클리드 호제법: 두 정수의 최대공약수 구하기

유클리드호제법은 두 정수의 최대공약수를 재귀적으로 구하는 방법입니다. 유클리드 호제법은 다음과 같습니다.

두 자연수 x, y 가 존재할 때, x, y의 최대공약수 gcd(x,y)는 다음과 같다.
y = 0 이면 최대공약수는 x
y != 0 이면 최대공약수는 gcd(y, x % y)

이를 파이썬 코드로 옮기면 다음과 같습니다.

def gcd(a: int, b: int) -> int:
    """두 정수 a, b의 최대공약수를 반환"""
    if b == 0:
        return x
    else:
        return gcd(b, a % b)

gcd()함수는 나누는 수(함수의 b자리)가 0이 될 때까지 재귀적으로 호출됩니다. 나머지가 0이 되면 마지막 재귀호출에서 나눠진 수가 최대공약수가 됩니다.

다만, 파이썬에서 최대공약수를 쓰고자할 때 라이브러리를 활용해서 함수를 사용하는 것이 더 편합니다.

import math

my_gcd = math.gcd(a,b)

재귀알고리즘의 분석

개론

재귀 알고리즘은 상향식 분석과 하향식 분석이 가능합니다.

하향식 분석

재귀알고리즘에서 처음으로 호출을 시작한 재귀함수에서 시작하여 가장 깊은 곳까지 분석하는 방법입니다. 얕은 곳(표면)에서 깊은 곳(최고 깊이)의 방향으로 분석하는 방법입니다.

상향식 분석

재귀 알고리즘의 재귀조건에서 시작하여 가장 상위의 방향으로의 흐름으로 알고리즘을 분석하는 방법입니다. 깊은 곳에서 얕은 곳의 방향으로 분석하는 방법입니다.

재귀 알고리즘의 비재귀적 표현

꼬리 재귀 제거하기

재귀 알고리즘에서 가장 끝에 있는 재귀함수를 제거합니다. 꼬리 재귀 함수의 의미를 정리를 하면 종류가 동일한 함수에 인수를 갱신하여 시작합니다.
```
 def recur(n:int):
     if n > 0:
         recur(n - 1)
         print(n)
         n = n - 2 
         # 인수를 갱신 후 동일한 재귀함수에 인수로 대입
         #        ... 생략...
```
재귀 제거하기

꼬리 재귀함수와는 다르게 중간에 있는 재귀함순는 제거하기가 쉽지 않습니다. 이후의 코드에 영향을 줄 수 있기 때문입니다. 패턴에 따라 스택이나 큐로 해결합니다.

저작자표시 비영리 변경금지