재귀 호출
함수 안에서 자기 자신을 호출하는 방식이다.
알고리즘을 구현할 때 반복문으로 구현한 코드보다 재귀호출로 구현한 코드가 더 직관적이고 이해하기 쉬운 경우가 종종 있다.
재귀호출 사용
def hello():
print("Hello, World!")
hello()
# 결과값
# Hello World!
# Hello World!
# Hello World!
# ... 1000번 무한 반복재귀호출이 종료되지 않으면 최대 재귀 깊이를 초과할 때 에러 발생
파이썬의 최대 재귀 깊이(maximum recursion depth) : 1000
재귀호출에 종료 조건 만들기
def hello(count):
if count == 0: # 종료 조건, count가 0일 때 종료
return
print("Hello World!", count)
count -= 1 # count를 1감소 시킨뒤 다시 hello에 넣음
hello(count)
# 결과값
# Hello World! 5
# Hello World! 4
# Hello World! 3
# Hello World! 2
# Hello World! 1실행 순서
hello(5) -> hello(4) -> hello(3) -> hello(2) -> hello(1) -> hello(0)
종료 순서
hello(0) -> hello(1) -> hello(2) -> hello(3) -> hello(4) -> hello(5)
팩토리얼 구하기
1부터 n까지 양의 정수를 차례대로 곱한 값을 팩토리얼 이라고 한다.
! 기호로 표기한다.
팩토리얼을 구하는 방식
1. 반복문
def factorial(n):
output = 1
# 반복문으로 숫자를 더하기
for i in range(1, n + 1):
output *= i
return output
print(factorial(5))
# 결과값
# 120
2.재귀함수
def factorial(n):
if n == 1: # n 이 1일때, 1을 반환하고 재귀호출 종료
return 1
return n * factorial(n - 1) # n과 factorial 함수에 n - 1을 넣어서 반환된 값을 곱하기
print(factorial(5))
# 결과값
# 120
# factorial 함수 연산 과정
# 5 * factorial(4)
# 4 * factorial(3)
# 3 * factorial(2)
# 2 * factorial(1)
# return 1
# 2 * 1
# 3 * 2
# 4 * 6
# 5 * 24
재귀함수의 문제점
상황에 따라서 같은 것을 기하급수적으로 많이 반복하게 된다.
따라서 이 문제를 위해서 메모화(memorization)를 사용하는것이 좋다.
피보나치 수열
0과 1로 시작해서 다음번 숫자는 두 앞의 두 피보나치 수의 합이 나오는 수열이다.
# 피보나치 수열 : 0과 1로 시작해서 다음번 수는 바로 앞의 두 피보나치 수의 합
def fibonacci(n):
if n == 1 or n == 2:
return 1
else:
return fibonacci(n - 1) + fibonacci(n - 2)
fibonacci(10)
# 결과값
# 55counter = 0
def fibonacci(n):
print(f"fibonacci({n})를 계산중")
global counter
counter += 1
# 피보나치 구하기
if n == 1 or n == 2:
return 1
else:
return fibonacci(n - 1) + fibonacci(n - 2)
fibonacci(10)
print(counter)
# 결과값
# 109
# fibonacci(10)를 계산중
# fibonacci(9)를 계산중
# fibonacci(8)를 계산중
# fibonacci(7)를 계산중
# fibonacci(6)를 계산중
# fibonacci(5)를 계산중
# fibonacci(4)를 계산중
# ...
# fibonacci(2)를 계산중
# fibonacci(1)를 계산중
# fibonacci(2)를 계산중
55이처럼 재귀함수는 한번 구했던 값이라도 처음부터 다시 계산해야 하기때문에 계산 횟수가 기하급수적으로 늘어나게된다.
따라서 이와같은 상황을 만들지 않기 위해서 메모화를 사용한다.
memo_dict = {1 : 1, 2 : 1}
def fibonacci(n):
if n in memo_dict:
# 메모가 되어 있으면 메모된 값을 리턴
return memo_dict[n]
else:
# 메모가 되어있지 않으면 값을 구함
output = fibonacci(n - 1) + fibonacci(n - 2)
memo_dict[n] = output
return output
fibonacci(50)
# 결과값
# 12586269025피보나치 수열을 구하는 방식을 처음 작성한 코드에서는 fibonacci(40) 을 구하는 시간이 상당히 오래 걸리지만 메모화를 만들면 fibonacci(1000)까지도 금방 값이 나오게 된다.
메모화를 위해서 딕셔너리를 사용해 한 번 계산한 값을 저장하였다.
딕셔너리에 값이 저장되어 있으면 처리를 수행하지 않고 곧바로 메모된 값을 반환하면서 코드의 실행 속도를 빠르게 하는 방식이다.
리스트를 평탄화 하는 재귀함수
리스트 평탄화는 중첩된 리스트가 있을 때 중첩을 모두 제거하고 풀어서 1차원 리스트로 만드는 것을 말한다.
def flatten(data):
output = []
for item in data:
# 리스트가 아니라면 output리스트에 자료를 넣고
# 리스트라면 리스트에 있는 요소들을 하나하나 output에 추가
if type(item) == list:
output.extend(item)
else:
output.append(item)
return output
example = [[1, 2, 3,], [4, 5, 6], 7, [8, 9]]
flatten(example)
# 결과값
# [1, 2, 3, 4, 5, 6, 7, 8, 9]
# 3차원이 되면 문제 발생
example = [[1, 2, 3,], [4, [5, 6]], 7, [8, 9]]
flatten(example)
# 결과값
# [1, 2, 3, 4, [5, 6], 7, 8, 9]리스트를 평탄화 하는 코드를 사옹했을 때 3차원 이상의 리스트가 나오면 리스트 평탄화가 제대로 작동되지 않는다.
3차원을 평탄화 하려면 코드를 수정해야 하고 그 이상으로 n차원의 리스트가 나온다면 코드의 수정이 얼마나 많이 수정되야 할지 감도 안온다. 이러한 상황을 만들지 않기 위해서 재귀함수를 사용해서 코드를 수정해주는것이 좋다.
# 재귀함수 사용
def flatten(data):
output = []
for item in data:
if type(item) == list:
output.extend(flatten(item))
else:
output.append(item)
return output
example = [[1, 2, 3], [4, 5, 6], 7, [8, 9]]
flatten(example)
# 결과값
# [1, 2, 3, 4, 5, 6, 7, 8, 9]
example = [[1, 2, 3], [4, [5, 6]], 7, [8, 9]]
flatten(example)
# 결과값
# [1, 2, 3, 4, 5, 6, 7, 8, 9]
example = [[1, 2, 3], [4, [5, [6, 7]]], [8, 9]]
flatten(example)
# 결과값
# [1, 2, 3, 4, 5, 6, 7, 8, 9]