재귀함수 - 파이썬(Python)
재귀함수란 함수 내에서 그 함수를 다시 사용하는 것을 말한다.
약간 인셉션 느낌이 드는 방식의 이 함수는 실제 코드를 보면 더 쉽게 이해될 수 있다.
def recursive():
print("이것은 재귀함수입니다.")
recursive()
recursive() #함수 호출
이 함수는 "이것은 재귀함수입니다." 를 무한히 출력하는 재귀함수이다.
recursive라는 재귀함수가 호출되면 print문을 수행하고 다시 recursive함수를 호출하는 모습이다.
하지만, 재귀적으로 진행되는 함수들은 모두 메모리의 스택에 지속적으로 쌓인 후 하나씩 pop하는 형식으로 실행된다.
그러나, 이렇게 쌓이는 데이터가 컴퓨터가 제어해놓은 스택의 제한(recursion depth라고도 부른다)을 초과하게 되면 해당 함수는 자동으로 종료된다. 일종의 무한루프를 끊어주는 용도라고 볼 수 있겠다.
재귀함수는 이론적으로 모든 for문이나 while문을 사용하는 반복문을 대신해서 사용될 수 있다.
반복문을 재귀함수로 사용하게 되면 보다 간결한 코드 작성이 가능해진다.
재귀함수를 이용해 작성할 수 있는 몇 가지 함수에 대해 알아보자.
1) 팩토리얼(Factorial) 함수
팩토리얼은 !를 기호로 사용해 특정 n 부터 1까지를 곱한 값을 구할 때 사용된다.
즉, 5! = 5 * 4 * 3 * 2 * 1 = 120이 되는 것이다.
팩토리얼 함수는 반복문과 재귀함수 모두로 구할 수 있다.
# 팩토리얼 반복문
def factorial(n):
result = 1
for i in range(1, n + 1):
result *= i
return result
# 팩토리얼 재귀함수
def recursive_factorial(n):
if n <= 1:
return 1
return n * recursive_factorial(n-1)
print(factorial(5))
print(recursive_factorial(5))
두 함수 모두 동일한 값이 출력됨을 알 수 있다.
재귀함수를 쓸 때 중요한 것은, 부분계산을 잘 찾아내는 것이다.
예를 들어, 5!은 사실 5 * 4! 이다. 그리고 4! 또한 4 * 3! 이다.
이것을 활용한 코드가 n * recursive_factorial(n-1) 이 되는 것이다.
여기서 n이 0이거나 1일 때, 팩토리얼 0!, 1! 의 값은 모두 1이므로, 해당 부분만 return 값을 1로 처리해주면 되겠다.
2) 유클리드호제법
유클리드 호제법은 두 값 A와 B의 최대공약수를 구하기 위해 사용되는 로직 중 하나이다.
이 알고리즘의 전제는 A와 B의 최대공약수는 B와 A%B의 최대공약수와 같다는 것이다. (A > B 라고 가정)
이것의 수학적 증명은 '유클리드 호제법 증명'과 같은 키워드로 구글링 해보면 쉽게 알 수 있다.
# 유클리드 호제법 반복문
def gcd(a, b):
while a % b != 0:
a, b = b, a % b
return b
# 유클리드 호제법 재귀함수
def recursive_gcd(a, b):
if a % b == b:
return b
return recursive_gcd(b, a % b)
둘 다 간단한 방식이다. 하지만, 파이썬에서는 이를 아주 편하게 함수로 만들어놨다.
from math import gcd
gcd 함수에 파라미터로 a, b 값을 넣어주기만 하면 된다.
3) 피보나치 수열
피보나치 수열은 n번째 값이 (n-2)번째 값과 (n-1)번째 값을 더한 값임을 만족하는 수열이다.
즉, 1, 1, 2 (1+1), 3 (1+2), 5 (2+3), 8 (3+5), ..... 와 같은 수열이다.
피보나치 수열을 구현하는 함수 역시 재귀함수로 구현 가능하다.
def fib(n): # 피보나치 수열의 n번째 항의 값을 출력해주는 반복문 함수
prev = 0
crt = 1
for i in range(n-1):
temp = prev
prev = crt
crt = prev + temp
return crt
def recursive_fib(n): # 피보나치 수열의 n번째 항의 값을 출력해주는 재귀함수
if n <= 2: # n = 1, 2 일때의 값은 1이므로
return 1
return f(n-1) + f(n-2)
for i in range(1, 11): # 1 ~ 10항까지 피보나치 수열 출력
print(recursive_fib(i))
