[자료구조 & 알고리즘] 5. 재귀 (Recursion)

재귀 (Recursion)

1. 재귀 함수

• 자신을 정의할 때 자기 자신을 재참조하는 함수를 재귀 함수라고 함.

public int factorial(int i) {
	if(i == 1) return 1;
	return i * factorial(i-1);
}

public int fibonacci(int i) {
	if(i == 1 || i == 2) return 1;
	return fibonacci(i-1) + fibonacci(i-2);
}

• 재귀의 구성 요소

     - 점화식(Recurrence Relation) : f(n)을 f(n-1), f(n-2), ..., f(2), f(1)의 관계식으로 표현하는 것

     - 탈출 조건(Base Case)

          - 더 이상 재귀 호출을 하지 않아도 값을 반환할 수 있는 상황(조건)

          - 모든 입력 값이 최종적으로 Base Case에 도달해야 함.

          - Base Case가 있어야 재귀 함수의 무한 루프를 방지할 수 있음.

• 시간 복잡도

     - (재귀 함수의 전체 시간 복잡도) = (재귀 함수 호출 수) x (재귀 함수 하나당 시간 복잡도)

     - f(n) = f(n-1) + n 과 같은 식으로 점화식에 재귀가 한 번이라면 O(n)

     - f(n) = f(n-1) + f(n-2) 와 같은 식으로 점화식에 재귀가 두 번이라면 O(2ⁿ)