Python에서의 재귀 알고리즘 이해와 예제

재귀 알고리즘은 함수가 자기 자신을 호출하여 문제를 해결하는 방식을 말합니다. Python은 재귀적 구현이 간단하고 직관적이어서 학습 및 사용이 용이합니다. 여기서는 재귀의 기본 개념을 이해하고, 몇 가지 기본적인 재귀 알고리즘 예제를 제공하겠습니다.

 

팩토리얼 계산하기

팩토리얼은 기본적인 재귀 함수의 예입니다. n!은 n * (n-1) * ... * 1과 같으며, n이 0일 때 1이 반환되는 base case를 가집니다. 이를 재귀적으로 구현하면 다음과 같습니다:

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

 

 

피보나치 수열

피보나치 수열은 다음 수가 앞의 두 수의 합으로 이루어지는 수열로, 재귀적 접근이 가능합니다. 피보나치 수열의 n번째 수를 찾는 재귀 함수는 다음과 같이 작성할 수 있습니다:

 

def fibonacci(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci(n-1) + fibonacci(n-2)

 

 

하노이의 탑

하노이의 탑 문제는 재귀 알고리즘을 이해하기에 적합한 예제입니다. 세 개의 기둥과 n개의 다양한 크기의 원판을 사용하여, 모든 원판을 한 기둥에서 다른 기둥으로 옮기는 문제입니다. 이 과정에서 큰 원판이 작은 원판 위에 있어서는 안 됩니다. 코드는 다음과 같습니다:

 def hanoi(n, source, target, auxiliary):
    if n == 1:
        print(f"Move disk 1 from {source} to {target}")
        return
    hanoi(n-1, source, auxiliary, target)
    print(f"Move disk {n} from {source} to {target}")
    hanoi(n-1, auxiliary, target, source)

 

 

재귀 알고리즘은 간결하고 이해하기 쉬운 코드를 작성할 수 있게 해 주지만, 매우 큰 입력 값에 대해서는 스택 오버플로우를 일으킬 수 있습니다. Python에서는 재귀 호출의 깊이가 기본적으로 1000으로 제한되어 있으나, sys.setrecursionlimit()을 사용하여 이 한계를 조정할 수 있습니다.

이러한 예제들은 재귀 알고리즘의 기본을 이해하고, Python으로 실제 문제를 해결하는 데 필요한 기초를 제공합니다. 재귀는 복잡한 문제를 단순하고 우아하게 해결할 수 있는 강력한 방법이 될 수 있습니다.