파이썬 재귀 함수 완벽 가이드: 초보자도 쉽게 이해하는 방법

파이썬 재귀 함수 사용법

재귀(Recursion)는 초보자에게 다소 어렵게 느껴질 수 있는 주제입니다. 하지만 재귀의 정의를 명확히 이해하면 어렵다는 편견은 쉽게 사라집니다. 재귀란 함수가 자기 자신을 호출하는 프로그래밍 기법을 말합니다.

간단해 보이지 않나요? 재귀는 익숙해지면 결코 어려운 개념이 아닙니다.

이 튜토리얼에서는 재귀의 개념과 작동 원리를 살펴보고, 팩토리얼 함수 예제를 통해 재귀 프로그래밍을 시작하는 방법을 단계별로 알아보겠습니다.

재귀란 무엇인가?

재귀는 어떤 것을 그 자체의 관점에서 정의하는 방식입니다.

재귀 함수는 자기 자신을 반복적으로 호출하면서 문제를 해결합니다. 이러한 동작 방식은 파이썬을 비롯한 대부분의 주요 프로그래밍 언어에서 지원되며, 컴퓨터 과학과 데이터 과학에서 핵심적인 개념으로 자리 잡고 있습니다.

재귀는 문제를 더 작은 하위 문제로 나누어 해결할 수 있고, 모든 하위 문제가 동일한 공식을 사용할 때 특히 유용합니다. 이런 유형의 문제를 흔히 "재귀 알고리즘"이라고 부르며, 해결의 핵심은 이름 그대로 재귀에 있습니다.

반복문 vs 재귀

알고리즘을 해결하는 방법에는 반복(iterative)과 재귀(recursive) 두 가지가 있습니다.

반복 방식의 알고리즘은 "강력하지만 투박하다"고 평가받곤 합니다. 목적은 달성하지만, 가장 우아한 방식은 아니기 때문입니다. 재귀 알고리즘을 제대로 이해하려면 먼저 반복 함수에 대해 살펴볼 필요가 있습니다.

반복 함수는 루프를 사용해 문제를 해결하는 함수로, 루프가 끝날 때까지 루프 내부의 코드를 실행합니다. 반면 재귀 함수는 문제를 더 작은 단위로 나누고, 각 부분을 자기 자신을 호출함으로써 해결합니다.

팩토리얼: 반복문 예제

팩토리얼은 재귀와 반복적 사고를 보여주기에 좋은 예제입니다. 수학에서 팩토리얼은 어떤 수와 그 이하의 모든 자연수를 곱한 값을 의미합니다.

예를 들어 5의 팩토리얼은 5 * 4 * 3 * 2 * 1이고, 2의 팩토리얼은 2 * 1입니다.

팩토리얼을 계산하는 반복 함수는 다음과 같이 작성할 수 있습니다:

def factorial(number):
	total = 1
	for n in range(1, number + 1):
		total = total * n
	return total

이 함수는 for 루프를 사용해 1부터 지정한 숫자까지의 모든 수를 순회합니다. 각 반복마다 현재 숫자를 total에 곱합니다. 이제 함수를 호출해 팩토리얼을 구해 보겠습니다:

answer = factorial(4)
print(answer)

이 코드는 24를 반환합니다. 이 결과가 나오기까지 코드는 다음 과정을 거칩니다:

1 * 1 = 1
1 * 2 = 2
2 * 3 = 6
6 * 4 = 24

보시다시피 이 코드는 4를 그보다 작은 모든 수와 곱한 후 마지막으로 자기 자신까지 곱합니다.

이 코드는 잘 작동하지만, 유일한 단점은 다소 투박하다는 점입니다. 바로 이럴 때 재귀 함수가 빛을 발합니다.

팩토리얼: 재귀 예제

이번에는 팩토리얼을 계산하는 재귀 함수를 작성해 보겠습니다. 새 파이썬 파일을 열고 다음 코드를 입력하세요:

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

이 코드는 재귀 방식을 사용합니다. 함수가 실행되면 먼저 if 문이 실행되어, 함수에 전달된 숫자가 1과 같은지 확인합니다. 1이라면 함수는 1을 반환하고, 그렇지 않으면 해당 숫자의 팩토리얼을 계산합니다.

이 계산은 함수에 전달된 숫자에 이전 숫자의 팩토리얼을 곱하는 방식으로 이루어집니다. 함수는 "number"가 1이 될 때까지 계속 자기 자신을 호출하며, 호출될 때마다 "number"의 값은 1씩 줄어듭니다.

이번에는 숫자 4로 코드를 실행해 보겠습니다:

answer = factorial(4)
print(answer)

결과로 24가 반환됩니다. 이전 예제와 동일한 정답입니다. 반복문 대신 재귀로 문제를 해결한 것입니다.

아직 조금 더 설명이 필요하다면, 재귀의 또 다른 예제를 살펴보겠습니다.

피보나치 수열로 이해하는 재귀

피보나치 수열은 각 숫자가 앞의 두 숫자의 합으로 이루어지는 수열입니다. 이 수열은 0, 1, 1, 2, 3, 5, 8, 13 등으로 시작합니다.

이 수열은 두 수를 더해 다음 수를 구하므로, 재귀를 적용하기에 완벽한 예제입니다.

파이썬 파일을 열고 다음 코드를 입력해 보세요:

def fibonacci(number):
	if number <= 1:
		return number
	else:
		return(fibonacci(number - 1) + fibonacci(number - 2))

이 코드는 "number"가 1보다 큰 동안 앞의 두 숫자의 합을 계산하고, 그렇지 않으면 "number"를 그대로 반환합니다. 이제 함수를 호출해 보겠습니다:

executions = 5

print("Fibonacci Sequence:")
for number in range(executions):
	print(fibonacci(number))

executions 변수는 피보나치 수열에서 몇 개의 숫자를 계산할지 결정합니다. 이 값을 사용해 for 루프를 만들고, 0부터 executions 값 범위 내의 각 숫자에 대해 fibonacci() 함수를 호출합니다.

for 루프가 시작되기 전에 콘솔에 "Fibonacci Sequence:"를 출력합니다. 이 예제에서 for 루프는 다음을 실행합니다:

fibonacci(1)
fibonacci(2)
fibonacci(3)
fibonacci(4)
fibonacci(5)

전체 코드를 실행하면 다음과 같은 결과가 출력됩니다:

Fibonacci Sequence:
0
1
1
2
3

코드가 피보나치 수열의 처음 다섯 개 숫자를 계산했습니다. executions 값을 늘리면 더 많은 숫자를 계산할 수 있습니다.

재귀 깊이와 기저 조건

재귀 함수에는 반드시 기저 조건(base condition)이 있어야 합니다. 기저 조건은 특정 조건이 충족되면 재귀를 멈추는 역할을 합니다. 기저 조건이 없으면 무한 루프가 발생합니다.

재귀 함수는 기본적으로 최대 1,000번까지 자기 자신을 실행할 수 있습니다. 이 한도에 도달하면 다음과 같은 오류가 발생합니다:

RecursionError: maximum recursion depth exceeded

앞서 작성한 피보나치 프로그램의 기저 조건은 다음과 같습니다:

...
if number <= 1:
		return number
…

이 조건은 피보나치 함수 내의 "number" 값이 1 이하인지 확인합니다. 1 이하라면 "number"를 반환하고, 그렇지 않으면 재귀 함수가 실행됩니다.

재귀를 사용해야 하는 이유

반복 함수 대신 재귀를 사용하면 어떤 장점이 있을까요? 기술적으로 두 방법 모두 동일한 결과를 얻을 수 있습니다. 재귀의 가장 큰 장점은 코드를 읽기 쉽다는 점입니다.

재귀 함수를 보면 문제의 해답이 문제를 더 작은 단위로 나누는 데 있다는 것이 명확하게 드러납니다. 반복 루프가 때로 더 빠를 수 있지만, 가독성 때문에 재귀 함수가 선호되는 경우가 많습니다.

재귀 함수는 읽기 쉽기 때문에 유지보수와 디버깅도 더 쉽습니다. 이해하기 어려운 복잡한 알고리즘을 작성할 때 특히 유용합니다.

마무리

재귀 함수는 문제의 해답을 찾기 위해 자기 자신을 호출하는 함수입니다.

재귀 함수는 문제를 여러 부분으로 나누고, 반복마다 문제의 한 부분씩 해결합니다. 재귀 함수는 팩토리얼 계산이나 피보나치 수열의 숫자를 구하는 데 널리 사용되며, 다양한 알고리즘에서도 활용됩니다.

이제 파이썬에서 재귀 함수를 활용할 준비가 되었습니다.