목차
재귀 함수
재귀 함수는 문제를 해결하기 위해 자신을 호출하여 문제를 더 작은 하위 문제로 나누는 함수입니다. 문제를 해결하는 프로세스에는 기본 사례 또는 중지 조건에 도달할 때까지 반복되는 자체 호출이 포함되며, 이 시점에서 함수는 자신을 다시 호출하지 않고 결과를 반환합니다. 재귀 함수는 특정 문제를 해결하는 우아하고 간결한 방법일 수 있지만 신중하게 구현하지 않으면 성능 문제나 스택 오버플로 오류가 발생할 수도 있습니다.
다음은 숫자의 펙토리얼을 계산하는 재귀 함수의 예입니다.
def factorial(n):
if n == 0 or n == 1:
return 1 # Base case
else:
return n * factorial(n - 1) # Recursive call
result = factorial(5)
print(result) # Output: 120
이 예에서 factorial 함수는 인수 n - 1로 자신을 호출하여 숫자 n의 펙토리얼을 계산합니다. 기본 사례는 n이 0 또는 1인 경우이며, 이 경우 함수는 자신을 다시 호출하지 않고 1을 반환합니다. 'n'의 펙토리얼은 기본 케이스에 도달할 때까지 'n'에 'n - 1'의 펙토리얼 등을 곱하여 계산됩니다.
재귀 프로세스를 더 잘 이해하기 위해 factorial(5)의 계산을 살펴보겠습니다.
factorial(5) = 5 * factorial(4)
factorial(4) = 4 * factorial(3)
factorial(3) = 3 * factorial(2)
factorial(2) = 2 * factorial(1)
factorial(1) = 1(기본 케이스)
함수 호출은 역순으로 해결됩니다.
factorial(2) = 2 * 1 = 2
factorial(3) = 3 * 2 = 6
factorial(4) = 4 * 6 = 24
factorial(5) = 5 * 24 = 120
재귀 함수를 사용할 때 스택 오버플로 오류로 이어질 수 있는 무한 재귀를 피하기 위해 기본 사례 또는 중지 조건을 정의하는 것이 중요합니다. 또한 일부 문제는 성능 문제로 인해 재귀에 적합하지 않을 수 있으며 이 경우 반복 솔루션이 더 적합할 수 있습니다.
팩토리얼을 구현하는 2가지 방법
1. 루프 사용(반복 방법)
반복 방법에는 루프를 사용하여 주어진 숫자의 팩토리얼을 계산하는 것이 포함됩니다. for 루프를 사용하여 각 정수를 1에서 n까지 곱할 수 있습니다.
def factorial_iterative(n):
result = 1
for i in range(1, n + 1):
result *= i
return result
n = 5
result = factorial_iterative(n)
print(f"{n}! = {result}") # Output: 5! = 120
이 예제에서는 정수 n을 입력으로 사용하는 factorial_iterative 함수를 정의합니다. 이 함수는 변수 result를 1로 초기화한 다음 for 루프를 사용하여 1에서 n(포함)까지 반복합니다. 각 반복에서 루프 변수 i는 result의 현재 값과 곱해져 값이 업데이트됩니다.
2. 재귀 함수 사용
재귀 함수는 문제를 해결하기 위해 자신을 호출하여 문제를 더 작은 하위 문제로 나누는 함수입니다. 재귀를 사용하여 n = 0 또는 n = 1(0! = 1! = 1이므로)에 대한 기본 사례를 사용하여 숫자의 팩토리얼을 계산할 수 있습니다. 아래 예시는 처음 보여드렸던 팩토리얼 예시와 동일합니다.
def factorial_recursive(n):
if n == 0 or n == 1:
return 1 # Base case
else:
return n * factorial_recursive(n - 1) # Recursive call
n = 5
result = factorial_recursive(n)
print(f"{n}! = {result}") # Output: 5! = 120
이 예에서 factorial_recursive 함수는 인수 n - 1로 자신을 호출하여 숫자 n의 팩토리얼을 계산합니다. 기본 사례는 n이 0 또는 1인 경우이며, 이 경우 함수는 자신을 다시 호출하지 않고 1을 반환합니다. 'n'의 팩토리얼은 기본 케이스에 도달할 때까지 'n'에 'n - 1'의 팩토리얼 등을 곱하여 계산됩니다.
두 방법 모두 숫자의 팩토리얼을 계산하는 데 사용할 수 있지만 일반적으로 반복 방법이 더 효율적이고 큰 n 값에 대한 스택 오버플로 오류가 덜 발생합니다. 반면에 재귀 방법은 일부 사람들에게 더 우아하고 이해하기 쉬울 수 있습니다.
피보나치 수열
피보나치 수열은 처음 두 수 이후의 각 숫자가 앞의 두 숫자의 합인 일련의 숫자입니다. 수열은 일반적으로 0과 1로 시작하며 다음과 같이 진행됩니다.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...
수학적 용어로 피보나치 수열은 다음과 같은 점화식으로 정의됩니다.
F(n) = F(n-1) + F(n-2)
초기 조건:
F(0) = 0, F(1) = 1
피보나치 수열을 재귀 함수로 구현하려면 정수 n을 입력으로 받고 n번째 피보나치 숫자를 반환하는 함수를 만듭니다. 함수는 인수 n-1 및 n-2로 자신을 호출한 다음 결과를 합산하여 n번째 피보나치 숫자를 계산합니다. 함수의 기본 경우는 n이 0 또는 1인 경우로, 이 경우 해당 피보나치 숫자를 직접 반환합니다.
n번째 피보나치 숫자를 찾기 위한 재귀 함수의 예는 다음과 같습니다:
def fibonacci_recursive(n):
if n == 0:
return 0 # 기본 경우: F(0) = 0
elif n == 1:
return 1 # 기본 경우: F(1) = 1
else:
return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2) # 재귀 호출
n = 10
result = fibonacci_recursive(n)
print(f"Fibonacci({n}) = {result}") # 출력: Fibonacci(10) = 55
이 예제에서 fibonacci_recursive 함수는 위에서 언급한 점화식을 사용하여 n번째 피보나치 숫자를 계산합니다. 함수는 n이 0 또는 1과 같은 기본 경우를 가지며, 다른 n 값에 대해 자신을 재귀적으로 호출합니다.
이 재귀 구현은 n의 값이 커질수록 상당히 느려지고 비효율적이 될 수 있다는 점에 유의해야 합니다. 이 경우 반복 루프, 메모이제이션 또는 행렬 거듭제곱과 같은 대안 방법을 사용하여 성능을 개선할 수 있습니다.
다음은 재귀 함수 코드를 작성하면서 발생할 수 있는 일반적인 실수와 그 예시입니다.
1. 베이스 케이스 누락: 재귀 함수를 작성할 때 고려해야 하는 첫 번째 것은 베이스 케이스입니다. 베이스 케이스는 재귀 호출이 종료되는 조건을 정의합니다. 이를 빼먹으면 함수가 무한정 자기 자신을 호출하게 되어 스택 오버플로우가 발생할 수 있습니다.
예시:
def factorial(n):
# 베이스 케이스 누락
return n * factorial(n - 1)
수정:
def factorial(n):
if n == 0: # 베이스 케이스
return 1
return n * factorial(n - 1)
2. 잘못된 베이스 케이스: 잘못된 베이스 케이스를 정의하면 예상치 못한 결과 또는 런타임 오류가 발생할 수 있습니다.
예시:
def factorial(n):
if n == 1: # 잘못된 베이스 케이스
return 0
return n * factorial(n - 1)
수정:
def factorial(n):
if n == 0: # 올바른 베이스 케이스
return 1
return n * factorial(n - 1)
3. 재귀 호출을 빼먹는 것: 재귀 함수는 수정된 인수로 자기 자신을 호출해야 합니다. 재귀 호출을 빼먹으면 함수가 예상한 대로 동작하지 않을 수 있습니다.
예시:
def sum_natural_numbers(n):
if n == 1:
return 1
# 재귀 호출을 빼먹음
수정:
def sum_natural_numbers(n):
if n == 1:
return 1
return n + sum_natural_numbers(n - 1) # 재귀 호출
4. 재귀 호출용 인수를 업데이트하지 않는 것: 재귀 호출할 때 함수가 베이스 케이스로 수렴하도록 인수를 올바르게 수정해야 합니다.
예시:
def factorial(n):
if n == 0:
return 1
return n * factorial(n) # 인수를 업데이트하지 않음
수정:
def factorial(n):
if n == 0:
return 1
return n * factorial(n - 1) # 인수를 올바르게 업데이트
'Python > Python 기본' 카테고리의 다른 글
[Python] 파이썬 튜플(tuple)이란? (2) | 2023.04.30 |
---|---|
[Python] 재귀 함수란? (2) (2) | 2023.04.30 |
[Python] 리턴 값(return value)이란? (0) | 2023.04.29 |
[Python] 파이썬에서 함수와 매개 변수 (2) (0) | 2023.04.28 |
[Python] 파이썬에서 함수와 매개 변수 (1) (0) | 2023.04.27 |