[08-1] 재귀(Recursion)란?

재귀.

파이썬 공부를 할 때, 재귀함수를 배우면서 아~뭔지 알겠다 하면서도 딥~하게 들어가면 정신을 못차렸다.

그래서 거리를 두고 지냈는데

재귀는 코딩 테스트에서 단독으로 나올정도로 중요하다. 그리고 이진탐색, 깊이, 완전 탐색 등 많은 부분에서 응용되어 활용된다.

트리, 그래프에서도 사용되니.. 재귀가 얼마나 중요한지 알겠지?

 

재귀함수란?

자기 자신을 재참조 하는 함수를 뜻한다.

 

재귀함수의 구성요소는 2가지가 있다.

1. 점화식: 호출하는 관계식으로 f(n) = f(n-1), f(n-2)... 이렇게 계속해서 표현하는 것

2. base case: 호출하지 않아도 게산값을 반환하는 상황

 

코드로 살펴보자.

def factorial(n):
	if n==1:
	  return 1 #base case
        return n* factorial(n-1) #점화식

 

factorial(n)이 계속 호출되는 것을 점화식이고, return에서 호출하지 않는 값을 반환한다. 

base case가 있어야 재귀함수의 무한루프를 탈출할 수 있다.

다만 n이 음수가 된다면? 무한으로 빠지겠지만, 그러기 위해서 n≥1 이자, 정수다라는 조건을 줄 것이다.

 

핵심은 base case에 도달할 수 있게 코드를 구현해야한다!

 

재귀함수의 시간복잡도는 재귀 함수 호출수 * 하나당의 시간복잡도

어디서 많이 보지 않았나? 바로 for 문과 유사하다. n에 비례하다면 O(n)일 것이고, 함수 2개를 호출함에 따라 2ⁿ에 비례하다면? O(2ⁿ)이 될 것이다.

재귀함수 시간 복잡도 사례

해당 사례처럼, 하나만 호출을 하는 재귀함수라면? O(n)이고, 2개 가지치기 형식으로 나눠진다면? O(2ⁿ)이 된다!

 

재귀함수 총정리

 

장점

1. 변수를 여럿 만들 필요 없다.

2. 코드가 엄청 간결해질 수 있다.

 

단점

1. 점화식과 base case를 꼭 생각해야 한다.

2. 구현의 난이도가 있는편이다.

 

총평

까다롭긴한데, 잘쓰면 좋은 성능을 냄