[자료구조] #12 Recursion(1)

• Recursion

 

Recursion = 재귀함수

단 몇개의 문자만으로 문제의 solution을 구할 수 있다.

다만 반드시 효율적이지는 않으며, 모든 문제가 재귀적으로 풀리지는 않는다.

 

• 일반적인 Format

 

1) Simple base case : 더 이상 재귀호출을 진행하지 않고 정답을 생성한다.

2) Recursive step : 함수가 재귀적으로 호출된다.

모든 재귀함수는 점진적으로 base case로 이동한다. 아니면 무한 loop에 빠진다.

 

만약 base case가 없다면?

스택이 용량이 초과되어 overflow error가 발생할 것이다.

 

• Recursion 푸는 방법

 

Divide & Conquer : 작은 문제로 나눠주고 각각 풀어준다.

우선 가정을 하고 설계한다!

 

그럼 어떻게 올바른 계산이 되는 것을 분석할 수 있을까?

수학적 귀납법을 이용하면 된다.(연쇄작용)

 

• 재귀함수 시간복잡도 분석

 

T(A)와 T(B)의 시간복잡도를 계산해서 비교해보자.

 

Base case : TA(n) = C

Recursive step : TA(n) = TA(n-1) + C

 

반복대치를 이용해 실제로 계산해보자.

 

n에 n-1을 대입해주자.

재귀함수의 시간복잡도 = 재귀적으로 정의된다 는 사실을 알수 있다.

 

결국 base case로 아래의 시간복잡도가 도출될 것이다.

 

 

n에 n/2를 대입해주자.

 

B도 base case로 아래의 시간복잡도가 도출되는 것을 확인할 수 있다.

 

A와 B의 시간복잡도를 비교해보면, B가 A보다 빠르다는 사실을 알 수 있다.