자료구조와 알고리즘 A+ 기원 5.

1. Recursion

: 자기 자신을 이용해서 문제를 풀어나가는 알고리즘 -> 함수(혹은 기타 알고리즘)에서 자기 자신을 호출

예를 들면 factorial 함수를 구현할 때는,

public long factorial(int n){
	if (n<0) {
		System.err.println("Number should be positive");
        System.exit(-1);
    if (n <= 1) return 1;
    else return n*factorial(n-1); // 자기 자신을 호출
}

-> 재귀는 자기 자신을 주어진 조건 안에서 계속해서 호출하기 때문에 StackOverflowError가 날 수 있다!

2. 시간복잡도

• T(n) = factorial(n)
  -> 즉 $O(n)$ = 하지만 항상 시간복잡도가 O(n)인 것은 아니고, 알고리즘마다 다르다($x^n$은 $O(log_n)$)

3. 예

• Fibonacci
• Hanoi
• Binary search (절반 자르고 계속해서 호출!)
• Trigonometric function
  - sin
  • cos