여기서 재귀 함수 호출에 보조 공간이 어떻게 필요한지 살펴보겠습니다. 일반 함수 호출과 어떻게 다른가요?
아래와 같은 함수가 있다고 가정해보세요. -
long fact(int n){
if(n == 0 || n == 1)
return 1;
return n * fact(n-1);
}이 함수는 재귀함수입니다. Fact(5)처럼 호출하면 아래와 같이 스택 내부에 주소가 저장됩니다. -
fact(5) ---> fact(4) ---> fact(3) ---> fact(2) ---> fact(1)
재귀 함수가 자신을 계속해서 호출하면 주소가 스택에 추가됩니다. 따라서 함수가 n번 재귀적으로 호출되면 O(n)개의 보조 공간을 차지하게 됩니다. 그러나 이는 일반 함수가 n번 호출된다고 해서 공간 복잡도가 O(n)이 된다는 의미는 아닙니다. 일반 함수의 경우 호출 시 주소가 스택에 푸시됩니다. 완료되면 주소가 스택에서 제거되고 호출자 함수에 입력됩니다. 그런 다음 다시 전화하십시오. 따라서 복잡도는 O(1)입니다.
위 내용은 C 프로그램에서 재귀 함수에 보조 공간을 사용합니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!
![[웹 프런트엔드] Node.js 빠른 시작](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
