재귀는 함수가 자신을 호출하는 프로세스입니다. 우리는 더 큰 문제를 더 작은 하위 문제로 해결하기 위해 재귀를 사용합니다. 명심해야 할 한 가지는 각 하위 문제가 동일한 종류의 패턴을 따르는 경우에만 재귀적 접근 방식을 사용할 수 있다는 것입니다.
재귀 함수는 두 부분으로 나뉩니다. 기본 케이스와 재귀 케이스. 기본 사례는 반복 작업을 종료하는 데 사용됩니다. 기본 케이스가 정의되지 않은 경우 함수는 (이론적으로) 무한 반복됩니다.
컴퓨터 프로그램에서 하나의 함수를 호출하면 프로그램 카운터의 값은 함수 영역으로 점프하기 전에 내부 스택에 저장됩니다. 작업을 완료한 후 주소를 표시하고 프로그램 카운터에 할당한 다음 작업을 다시 시작합니다. 재귀 호출 중에 주소를 여러 번 저장하고 다음 함수 호출 문으로 점프합니다. 하나의 기본 케이스가 정의되지 않으면 계속 반복되고 주소를 스택에 저장합니다. 스택에 더 이상 공간이 없으면 "내부 스택 오버플로" 오류가 발생합니다.
재귀 호출의 한 가지 예는 숫자의 계승을 찾는 것입니다. 우리는 숫자 n =n의 계승을 볼 수 있습니다! n * (n-1)!과 동일하고 다시 n * (n - 1) * (n - 2)!와 동일합니다. 따라서 계승이 함수이면 계속해서 호출되지만 인수는 1만큼 감소합니다. 인수가 1 또는 0이면 1을 반환합니다. 이것은 재귀의 기본 사례일 수 있습니다.
예
#include<iostream>
using namespace std;
long fact(long n){
if(n <= 1)
return 1;
return n * fact(n-1);
}
main(){
cout << "Factorial of 6: " << fact(6);
} 출력
Factorial of 6: 720