코드잇의 알고리즘의 정석 수업을 수강하고 정리한 글입니다.
정확하지 않거나 빠트린 내용이 있을 수 있기 때문에 강의를 수강하시길 권장합니다.
재귀 함수 (Recursive Function) : 자기 자신을 호출하는 함수
# 재귀 함수의 예
# 정수 n부터 1까지 출력하는 countdown 함수
def countdown(n):
if n > 0:
print(n)
countdown(n - 1)
countdown(4)
# 콘솔
4
3
2
1
# 실행 순서는 1-, 2-, 3- 이렇게 표현하였다.
# 프로그램 실행
def countdown(n):
if n > 0:
print(n)
countdown(n - 1)
countdown(4) # 1- countdown(4)가 실행된다.
# countdown(4)
if 4 > 0:
print(4) # 2- 4가 출력 된다.
countdown(4 - 1) # 3- countdown(3)이 실행된다.
# countdown(3)
if 3 > 0:
print(3) # 4- 3이 출력된다.
countdown(3 - 1) # 5- countdown(2)이 실행된다.
# countdown(2)
if 2 > 0:
print(2) # 6- 2가 출력된다.
countdown(2 - 1) # 7- countdown(1)이 실행된다.
# countdown(1)
if 1 > 0:
print(1) # 8- 1이 출력된다.
countdown(1 - 1) # 9- countdown(0)이 실행된다.
# countdown(0)
if 0 > 0: # 10- if문을 수행하지 않고 countdown(0)이 끝난다.
print(1) # 실행되지 않음
countdown(0 - 1) # 실행되지 않음
# 11- countdown(0)이 끝났으므로 countdown(1)이 끝난다.
# 12- countdown(1)이 끝났으므로 countdown(2)가 끝난다.
# 13- countdown(2)기 끝났으므로 countdown(3)이 끝난다.
# 14- countdown(3)이 끝났으므로 countdown(4)가 끝난다.
# 15- countdown(4)가 끝났으므로 프로그램이 종료된다.
재귀적으로 문제를 푼다는 것 = 부분 문제(Subploblem)의 답을 이용해서 기존 문제를 푸는 것
5!안에는 부분문제 4!()이 존재한다.
즉 5!을 풀기 위해서는 4!을 풀어야한다.
4!안에는 부분문제 3!()이 존재한다.
즉 4!을 풀기 위해서는 3!을 풀어야한다.
3!안에는 부분문제 2!()이 존재한다.
즉 3!을 풀기 위해서는 2!을 풀어야한다.
이와 같이 재귀적으로 문제를 해결할 수 있으며, 마지막에는 0!이 남게 된다.
우리는 0!이 팩토리얼 정의를 통해 1임을 이미 알고 있다. ()
0!에 1을 곱하면 1!이 풀리고 마찬가지로 1!에 2를 곱하면 2!이 풀린다. 이를 반복하면 5!문제도 풀 수 있으며 부분 문제를 먼저 풀어서 본연의 문제를 해결 할 수 있다.
재귀적으로 문제를 접근할 때는 base case와 recursive case로 나누어서 생각해야 한다. 우리는 5!의 문제를 재귀적으로 접근해보면서 임을 이미 알고 있었다. 이것을 base case로 보면 된다. base case, recursive case로 나누어서 문제에 접근하면 재귀적으로 문제에 접근하는데 수월하다.
base case:
인 경우
recursive case:
인 경우
# 재귀적으로 구현한 factorial 함수
def factorial(n):
if n == 0:
return 1
return factorial(n - 1) * n
print(factorial(4))
# 실행 순서는 1-, 2-, 3- 이렇게 표현하였다.
# @{{number}}는 하단에 있는 주석에서 위치를 표시하기 위해 사용되었다.
def factorial(n):
if n == 0:
return 1
return factorial(n - 1) * n
print(factorial(4)) # 1- factorial(4)가 실행된다. (@5)
# factorial(4)
if 4 == 0:
return 1
return factorial(4 - 1) * 4 # 2- factorial(3)이 실행된다. (@4)
# factorial(3)
if 3 == 0:
return 1
return factorial(3 - 1) * 3 # 3- factorial(2)가 실행된다. (@3)
# factorial(2)
if 2 == 0:
return 1
return factorial(2 - 1) * 2 # 4- factorial(1)이 실행된다. (@2)
# factorial(1)
if 1 == 0:
return 1
return factorial(1 - 1) * 1 # 5- factorial(0)이 실행된다. (@1)
# factorial(0)
if 0 == 0:
return 1 # 6- 1이 리턴된다.
return factorial(0 - 1) * 0
# 7- @1에서 factorial(1 - 1)이 1로 대체되고 $1\times1$이 되어 1을 리턴한다.
# 8- @2에서 factorial(2 - 1)이 1로 대체되고 $1\times2$이 되어 2을 리턴한다.
# 9- @3에서 factorial(3 - 1)이 2로 대체되고 $2\times3$이 되어 6을 리턴한다.
# 10- @4에서 factorial(4 - 1)이 6로 대체되고 $6\times4$이 되어 24을 리턴한다.
# 11- @5에서 리턴된 값인 factorial(4)가 24로 대체되고 이를 콘솔에 출력한다.
최종적으로 4!의 값인 24가 콘솔에 출력된다.
반복문은 재귀로 풀수 있고, 재귀 함수는 반복문으로 해결이 가능하다.
# 반복문을 이용한 팩토리얼
def factorial(n):
result = 1
for i in range(1, n+1):
result = result * 1
return result
# 재귀를 이용한 팩토리얼
def factorial(n):
if n == 0:
return 1
return factorial(n - 1) * n
보통 함수를 실행하면 원래의 위치를 기록해 두었다가 함수가 끝나면 그 위치로 돌아온다.
def say_hello(name)
print("hello " + name)
my_name = "Young"
say_hello(my_name) # 위치를 기록해둔다.
이렇게 함수의 위치를 기록해 두는 곳을 call stack이라고 하며, 재귀를 너무 많이 호출하면 call stack이 쌓이게 되고 과부하로 인해 프로그램이 중단될 수 있다.