C 프로그램에서 재귀 함수가 있는 보조 공간?

여기에서 재귀 함수 호출에 보조 공간이 어떻게 필요한지 살펴보겠습니다. 그리고 일반 함수 호출과 어떻게 다른가요?

아래와 같은 하나의 함수가 있다고 가정합니다 -

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)이 됩니다.