재귀함수 (Recursive Function)
자기 자신을 다시 호출하는 함수
재귀 함수의 종료 조건
재귀 함수를 문제 풀이에서 사용할 때는 재귀 함수가 언제 끝날 지, 종료 조건을 꼭 명시해야 한다. 다음 코드는 재귀 함수를 100번 호출하도록 작성한 코드이다.
def recursive_function(i):
# 100번째 호출을 했을 때 종료되도록 종료 조건 명시
if i == 100:
return
print(i, '번째 재귀함수에서', i + 1, '번째 재귀함수를 호출합니다.')
recursive_function(i + 1)
print(i, '번째 재귀함수를 종료합니다.')
recursive_function(1)
.
.
.
.
.
.
컴퓨터 내부에서 재귀 함수의 수행은 스택 자료구조를 이용한다. 함수를 계속 호출했을 때 가장 마지막에 호출한 함수가 먼저 수행을 끝내야 그 앞의 함수 호출이 종료되기 때문이다.
재귀 함수를 이용한 팩토리얼 예제
# 반복적으로 구현한 n!
def factorial_iterative(n):
result = 1
# 1부터 n까지의 수를 차례대로 곱하기
for i in range(1, n + 1):
result *= i
return result
# 재귀적으로 구현한 n!
def factorial_recursive(n):
if n <= 1: # n이 1 이하인 경우 1을 반환
return 1
# n! = n * (n - 1)!를 그대로 코드로 작성하기
return n * factorial_recursive(n - 1)
# 각각의 방식으로 구현한 n! 출력(n = 5)
print('반복적으로 구현:', factorial_iterative(5))
print('재귀적으로 구현:', factorial_recursive(5))반복문 대신 재귀 함수를 사용했을 때,
더 간결한 코드를 작성할 수 있다는 장점이 있다.
유클리드 호제법을 이용한 최대공약수 계산 예제
- 유클리드 호제법
두 자연수 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))실행 결과
6
📘 이것이 취업을 위한 코딩 테스트다 with 파이썬 :: chapter 05
