[자료구조/ 알고리즘] 재귀(Recursion)

참고사항💡 재귀는 추후 그래프 탐색, 트리, dp 등 주요 자료구조와 알고리즘에 접목되기에 중요하다!

재귀(Recursion)

자신을 정의할 때, 자기 자신을 재참조하는 것

대표적은 재귀로는 팩토리얼과 피보나치가 있다. 자기 자신을 재참조하는 것이 어떤 의미인지 아래 코드를 통해 확인해보자.

팩토리얼(fatorial)

함수 fatorial의 반환에 fatorial를 재참조하는 것을 확인할 수 있다.

function fatorial(n){
	if(n === 1) return 1;
	return n * fatorial(n - 1);
}

피보나치(fibonacci)

함수 fibo의 반환에 fibo를 재참조하는 것을 확인할 수 있다.

function fibo(n){
	if(n === 1 || n === 2) return 1;
	return fibo(n - 1) + fibo(n - 2);
}

---

재귀의 시간 복잡도

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

팩토리얼의 시간복잡도

• 재귀 함수 호출 수 ⇒ n
• 재귀 함수 하나 당 시간 복잡도 ⇒ O(1)
• 재귀 시간 복잡도 ⇒ O(n x 1)

피보나치의 시간복잡도

• 재귀 함수 호출 수 ⇒ 2ⁿ
• 재귀 함수 하나 당 시간 복잡도 ⇒ O(1)
• 재귀 시간 복잡도 ⇒ O(2ⁿ x 1)