[알고리즘 스터디] 재귀
2024. 4. 18. 19:11ㆍ카테고리 없음
728x90
재귀 (走递, recursion)는 자신을 정의하면서 자신을 재참조하는 방법입니다. 컴퓨터 과학에서, 이르려면 프로그래밍에 적용된 재귀 호출(recursive call)입니다. 함수 호출 栈을 사용해 호출된 함수의 호출 이력을 기억하고 관리하며, 재귀 함수의 반복적인 호출을 가능하게 합니다.
Call Stack(호출 스택)
호출 스택(Call Stack)은 프로그래밍 언어에서 함수 호출을 관리하는 보이지 않는 데이터 구조입니다. 호출된 함수는 다른 함수가 반환(return)될 때까지 기다리는 경우가 많으며, 이런 순서는 무작위가 아닙니다.
제일 먼저 호출한 함수가 있고, 그 함수 안에서 두 번째 함수를 호출하는 식으로 진행됩니다.
콜스택은 종이 더미와 유사한 개념으로, 함수를 호출하면 콜스택의 꼭대기에 쌓이게 됩니다.
함수가 호출되면 스택의 꼭대기에 추가되고, 함수가 반환(return)되면 꼭대기에서 제거됩니다.
이는 마치 책상 위에 있는 종이 더미에서 맨 위에 종이를 쌓고, 꺼낼 때는 꼭대기에서부터 꺼내는 것과 같습니다. 재귀 함수를 사용하면 콜스택을 많이 사용하게 됩니다.
일반 함수는 호출되면 바로 스택에서 제거되지만, 재귀 함수는 콜스택에 많은 함수 호출을 쌓은 후, 종료 지점에 도달하면 꼭대기부터 차례로 반환하면서 스택에서 제거됩니다.
재귀 호출 & 중단점
재귀함수는 두가지 조건이 있다.
- 자기 자신을 재귀적으로 호출할 것
- 중단점(종료조건)이 있을 것
종료 조건은 재귀 호출을 멈추는 시점을 정의하는 것으로, 이를 통해 무한 재귀를 방지할 수 있습니다. 종료 조건이 없다면 재귀 함수는 계속해서 자기 자신을 호출하게 되어 스택 오버플로우(stack overflow) 오류가 발생할 수 있습니다.
function sum(n) {
// 종료 조건: n이 1 이하일 때 n을 반환
if (n <= 1) {
return n;
}
// 자기 자신을 재귀적으로 호출
return n + sum(n - 1);
}종료 조건: if (n <= 1)은 종료 조건으로, n이 1 이하일 때 재귀 호출을 멈추고 n을 반환합니다.
재귀 호출: return n + sum(n - 1)은 자기 자신을 재귀적으로 호출하는 부분입니다. n과 sum(n - 1)의 결과를 더해서 반환합니다.
재귀 중 유명한 예시로 피보나치 수열이 있다.
#include <iostream>
int fibonacci(int n) {
// 종료 조건: n이 0 또는 1일 때 n을 반환
if (n <= 1) {
return n;
}
// 자기 자신을 재귀적으로 호출
return fibonacci(n - 1) + fibonacci(n - 2);
}
int main() {
int n;
std::cout << "피보나치 수열의 항 번호를 입력하세요: ";
std::cin >> n;
std::cout << "피보나치 수열의 " << n << "번째 항은 " << fibonacci(n) << "입니다." << std::endl;
return 0;
}
위 코드에서 fibonacci 함수는 피보나치 수열의 n번째 항을 계산하는 재귀 함수입니다.
종료 조건: if (n <= 1)은 종료 조건으로, n이 0 또는 1일 때 재귀 호출을 멈추고 n을 반환합니다.
재귀 호출: return fibonacci(n - 1) + fibonacci(n - 2)는 자기 자신을 재귀적으로 호출하는 부분입니다.
피보나치 수열의 n번째 항은 이전 두 항의 합이므로, fibonacci(n - 1)과 fibonacci(n - 2)를 재귀적으로 호출하여 그 결과를 더해서 반환합니다.
main 함수에서는 사용자로부터 피보나치 수열의 항 번호를 입력받아 fibonacci 함수를 호출하고, 그 결과를 출력합니다.
예를 들어, 사용자가 6을 입력하면 fibonacci(6)이 호출되고, 다음과 같은 과정을 거쳐 8을 반환합니다:
728x90