def recursive_function():
print('재귀 함수를 호출합니다.')
recursive_function()
recursive_function()
코드를 실행 하면 ‘재귀 함수를 호출합니다.’라는 문자열을 무한히 출력한다.
정의된 recursive_function()이 자기 자신을 계속해서 호출하기 때문에 무한루프에 빠지게 된다.
재귀 함수의 종료 조건
재귀 함수를 문제 풀이에서 사용할 때는 재귀 함수가 언제 끝날지, 종료 조건을 꼭 명시해야 한다.
종료 조건을 명시하지 않으면 함수가 무한 호출될 수 있다.
def recursive_function(i):
# 100 번째 출력했을 때 종료되도록 종료 조건 명시
if i == 100:
return
print(i, '번째 재귀함수에서', i + 1, '번째 재귀함수를 호출합니다.')
recursive_function(i + 1)
print(i, '번째 재귀함수를 종료합니다.')
recursive_function(1)
컴퓨터 내부에서 재귀 함수의 수행은 스택 자료구조를 이용한다.
함수를 계속 호출했을 때 가장 마지막에 호출한 함수가 먼저 수행을 끝내야 그 앞의 함수 호출이 종료되기 때문이다.
컴퓨터의 구조 측면에서 보자면 연속해서 호출되는 함수는 메인 메모리의 스택 공간에 적재되므로 재귀 함수는 스택 자료구조와 같다는 말은 틀린말이 아니다.!!
재귀 함수는 내부적으로 스택 자료구조와 동일하다는 것을 기억하자.
스택 자료구조를 활용해야 하는 상당수 알고리즘은 재귀 함수를 이용해서 간편하게 구현될 수 있다. DFS가 대표적인 예이다.
팩토리얼
재귀 함수를 이용하는 대표적인 예제는 팩토리얼 문제가 있다. 팩토리얼 기호는 느낌표(!)를 사용
n! = 1 x 2 x 3 x … x (n - 1) x n
수학적으로 0! 과 1!의 값은 1
def factorial_iterative(n):
result = 1
for i in range(1, n+1):
result *= i
return result
def factorial_recursive(n):
if n <= 1:
return 1
return n * factorial_iterative(n - 1)
print('반복적으로 구현:', factorial_iterative(5))
print('재귀적으로 구현:', factorial_recursive(5))
반복문 보다 재귀 함수의 코드가 더 간결해 진다.
재귀 함수가 수학의 점화식(재귀식)을 그대로 소스코드로 옮겼기 때문
수학에서 점화식은 특정한 함수를 자신보다 더 작은 변수에 대한 함수와의 관계로 표현한 것을 의미한다.
팩토리얼의 수학적 점화식 표현
n이 0혹은 1일 때: factorial(n) = 1
n이 1보다 클 때: factorial(n)= n * factorial(n-1)
최대 공약수 계산(유클리드 호제법)
두 개의 자연수에 대한 최대 공약수를 구하는 대표적인 알고리즘으로는 유클리드 호제법이 있습니다.
유클리드 호제법
두 자연수 A, B에 대하여 (A > B) A를 B로 나눈 나머지를 R이라고 합시다.
이때 A와 B의 최대공약수는 B와 R의 최대공약수와 같습니다.
유클리드 호제법의 아이디어를 그대로 재귀 함수로 작성할 수 있습니다.
# 최대공약수 유클리드 호제법
def gcd(a, b):
if a % b == 0:
return b
else:
return gcd(b, a % b)
print(gcd(192, 162))
재귀 함수 사용의 유의사항
재귀 함수를 잘 활용하면 복잡한 알고리즘을 간결하게 작성할 수 있다.
단, 오히려 다른 사람이 이해하기 어려운 형태의 코드가 될 수도 있으므로 신중하게 사용해야 한다.
모든 재귀 함수는 반복문을 이용하여 동일한 기능을 구현 가능
재귀 함수가 반복문보다 유리한 경우도 있고 불리한 경우도 있다.
컴퓨터가 함수를 연속적으로 호출하면 컴퓨터 메모리 내부의 스택 프레임에 쌓인다.
그래서 스택을 사용해야 할 때 구현상 스택 라이브러리 대신에 재귀 함수를 이용하는 경우가 많다.(DFS등)
