재귀 (Recursion)
재귀는 추후 그래프 탐색, 트리 , dp 등 주요 자료구조와 알고리즘에 접목되기에, 중요합니다. 우선 재귀의 정의에 대해 알아 보겠습니다.
재귀의 정의
자신을 정의할때, 자기 자신을 재참조하는 것
대표적인 재귀로는 factorial과 fibonacci가 있습니다. 자기 자신을 재참조한다는 것이 어떤 의미인지 코드를 통해 확인해보도록 합시다.
재귀의 example
팩토리얼(factorial)
def factorial(n):
if n == 1:
return 1
return n * factorial(n - 1)
Python
복사
함수 factorial의 반환에 factorial를 재참조 하는 것을 확인할 수 있습니다.
피보나치(fibonacci)
def fibo(n):
if n == 1 or n == 2:
return 1
return fibo(n - 1) + fibo(n - 2)
Python
복사
함수 fibo의 반환에 fibo를 재참조하는 것을 확인할 수 있습니다.
함수를 선언 해보았으니 각각의 함수가 어떻게 실행되는지 확인해보도록 합시다.
팩토리얼 함수의 실행
n이 5일 시 factorial 함수는 제어문에 걸리지 않고
5 * factorial(4)를 return 해줍니다.
이제 factorial(4) 를 실행 시켜야 합니다.
n이 4일 시 factorial 함수는 제어문에 걸리지 않고
4 * factorial(3)를 return 해줍니다.
이제 factorial(3)을 실행 시켜야 합니다.
n이 3일 시 factorial 함수는 제어문에 걸리지 않고
3 * factorial(2)를 return 해줍니다.
이제 factorial(2)을 실행 시켜야 합니다.
n이 2일 시 factorial 함수는 제어문에 걸리지 않고
2 * factorial(1)를 return 해줍니다.
이제 마지막으로 factorial(1)을 실행 시켜야 합니다.
n이 1일 시 factorial 함수는 제어문에 걸려 1를 return 해줍니다.
최종적으로 재귀를 통해서 5! = 120 인 것을 알 수 있습니다.
피보나치 함수의 실행
n이 4일 시 fibo 함수는 제어문에 걸리지 않고
fibo(3)+ fibo(2)를 return 해줍니다.
두 개의 fibo() 함수가 있는데, 우선 앞의 fibo(3)을 보도록 합시다.
fibo(3)은 n이 3으로서 다시,
fibo(2)+ fibo(1)를 return 해줍니다.
이제 fibo(2)와 fibo(1)들이 남았습니다.
fibo(2)와 fibo(1)은 제어문에 걸림으로써, 1을 return 합니다.
최종적으로 재귀를 통해서 4번째 피보나치 수는 3이 됩니다.
재귀의 수학적 접근
앞선 fibonacci와 factorial을 자세히 살펴보면, n번째 함수를 n-1번째 함수로 표현 하는 것을 알 수 있습니다. factorial의 경우, 로 표현 되고, fibonacci의 경우, 으로 표현 됩니다.
이러한 식을 우리는 recurrence relation(점화식) 이라고 합니다. 이것 역시 자기 자신을 참조하는 개념이 들어 있습니다. 그러나 계속 자기 자신을 참조하게 되면, 무한 루프에 빠질 수 있습니다.
무한 루프를 방지 해주도록 base case를 설정해주어야 합니다. base case는 더 이상 자기 자신을 재참조 하지 않는 상황을 의미합니다.
앞 선 factorial와fibonacci 의 상황으로 위 내용을 정리합시다.
def factorial(n):
if n == 1:
return 1
return n * factorial(n - 1)
Python
복사
•
reccurence relation
⇒
•
base case
⇒
def fibo(n):
if n == 1 or n == 2:
return 1
return fibo(n - 1) + fibo(n - 2)
Python
복사
•
reccurence relation
⇒
•
base case
⇒
재귀는 reccurence relation과 base case로 구성되는 것입니다. reccurence relation은 해답을 직관적으로 제공해주며, base case는 무한 루프를 방지해줍니다. 두 가지를 모두를 놓치지 않는 것이 재귀를 풀 때 있어 가져야 할 마음가짐입니다.
1.
식들의 관계를 생각해본다. (reccurence relation)
2.
인 경우를 생각해본다. (base case)
재귀의 시간 복잡도
시간 복잡도는 언제나 중요한 문제입니다.
재귀의 시간복잡도 = 재귀 함수 호출 수 x (재귀 함수 하나당) 시간복잡도
앞서서 다룬 factorial와 fibo의 시간 복잡도를 위 공식을 활용해서 구해보도록 하겠습니다.
def factorial(n):
if n == 1:
return 1
return n * factorial(n - 1)
Python
복사
•
재귀 함수 호출 수
⇒
•
재귀 함수 하나 당 시간복잡도
⇒
•
재귀의 시간 복잡도
⇒
def fibo(n):
if n == 1 or n == 2:
return 1
return fibo(n - 1) + fibo(n - 2)
Python
복사
•
재귀 함수 호출 수
⇒
•
재귀 함수 하나 당 시간복잡도
⇒
•
재귀의 시간 복잡도
⇒
Copyright 2023. 노씨데브. All rights reserved. 무단 공유 및 배포를 금합니다.