재귀

(구성요소 2가지)

- 점화식

: f(n)을 f(n-1), f(n-2) 등의 관계식으로 표현하는 것

 

- base case

: 더이상 재귀호출을 하지 않아도 계산값을 반환할 수 있는 조건

: 모든 입력이 최종적으로 base case을 이용해서 문제를 해결할 수 있어야 한다.

 

(시간 복잡도) = (재귀함수 호출 수) * (재귀함수 하나당 시간 복잡도)