Utiliser un espace auxiliaire pour les fonctions récursives dans le programme C ?

Ici, nous verrons comment les appels de fonctions récursifs nécessitent un espace auxiliaire. En quoi est-ce différent d’un appel de fonction normal ?

Supposons que nous ayons une fonction comme indiqué ci-dessous -

long fact(int n){
   if(n == 0 || n == 1)
      return 1;
   return n * fact(n-1);
}

Cette fonction est une fonction récursive. Lorsque nous l'appelons comme fact(5), il stockera l'adresse à l'intérieur de la pile comme indiqué ci-dessous -

fact(5) --->
fact(4) --->
fact(3) --->
fact(2) --->
fact(1)

Comme la fonction récursive s'appelle encore et encore, l'adresse est ajoutée à la pile. Par conséquent, si la fonction est appelée de manière récursive n fois, elle occupera un espace auxiliaire O(n). Mais cela ne signifie pas que si une fonction normale est appelée n fois, la complexité spatiale sera O(n). Pour les fonctions normales, l'adresse est poussée sur la pile lorsqu'elle est appelée. Une fois terminée, l'adresse est extraite de la pile et entrée dans la fonction de l'appelant. Puis rappellez. Sa complexité est donc O(1).

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!