[알고리즘] 재귀(Recursion)란?

📝 재귀 알고리즘이란?

하나의 함수에서 자기 자신을 다시 호출하여 작업을 수행하는 알고리즘이다.

재귀 함수의 구조

function recurse() {
    // function code
    recurse();
    // function code
}

recurse();

🎯 재귀 함수의 특징

• 스택처럼 호출한 함수를 쌓았다가 종료 조건을 만나면 위에서부터 하나씩 꺼내 처리하는 방식이다.
• 함수 호출을 중지하는 조건이 있어야 한다.
• 적용 예시) 1부터 n까지의 합 / !팩토리얼 / 최대공약수 문제 / 파보나치 수열 구하기 등

---

📈 재귀 함수의 장점

• 코드의 가독성이 높아진다. 재귀적 호출을 통해 코드를 간결하게 작성할 수 있다.
• 일부 알고리즘에서는 반복문을 사용하는 것보다 재귀 함수를 사용하는 것이 더 직관적이다.

📉 재귀 함수의 단점

• 함수를 호출할 때마다 스택에 새로운 프레임을 생성한다. 스택이 너무 깊어지게 되면 스택 오버플로우가 발생할 수 있다.
• 함수의 호출이 반복적으로 일어나기 때문에 일반적으로 반복문을 사용하는 것보다 느리다.

---

참고자료

• 자바스크립트 재귀
• [데이터 구조] 재귀(recursive) 란?
• [Java/알고리즘] 재귀 함수(Recursion Function) 이해하기