Qu'est-ce que la récursivité en langage C ? Partage d'exemples de fonctions récursives classiques

Qu'est-ce que la récursivité en langage C ? L'article suivant vous aidera à comprendre la récursivité en langage C à travers des exemples de fonctions récursives classiques. J'espère qu'il vous sera utile !

La récursion est une méthode d'un processus ou d'une fonction qui s'appelle directement ou indirectement dans sa définition ou sa description. Une fonction récursive est une méthode de directement ou indirectement ; s'appelant indirectement Appeler sa propre fonction signifie appeler son propre processus.

Les étudiants qui débutent dans la récursion peuvent avoir du mal à comprendre la récursivité. Il peut y avoir de nombreux points difficiles à comprendre, tels que :

• Pourquoi un. la fonction doit-elle être appelée en elle-même ? Et vous-même ?

• Puisque vous pouvez vous appeler, il doit y avoir de nombreuses couches imbriquées les unes dans les autres lors de l'opération récursive.

• Pendant l'opération récursive, les paramètres seront transmis entre plusieurs couches imbriquées les unes dans les autres. Les multiples couches s'influenceront-elles mutuellement ?

Deux éléments de récursion

• Limite de récursion

• La logique de la récursion - formule de récursion" "

Le processus récursif doit avoir des changements de paramètres, et les changements de paramètres sont liés à la limite de récursion.

Dans des questions plus difficiles, ces deux-là ne sont pas faciles à obtenez-le directement.

Les étudiants qui comprennent les différents problèmes de récursion peuvent être capables de les expliquer clairement en une phrase, mais les étudiants qui ne comprennent pas ne pourront pas les comprendre, peu importe ce qu'ils disent.

Ce qui suit est passé Quelques exemples simples pour [expérimenter] la récursion, comprenez d'abord la récursion d'un point de vue [perceptuel].

Nombre de Fibonacci

On arrive à la récursion du nombre de Fibonacci La formule est : F(0)=F(1)=1,F(n)=F(n-1)+F(n-2) n>=2;

Cela donne évidemment la valeur de F(n) lorsque la limite de récursion n=0 ou 1, et la logique récursive F(n)=F(n-1)+F(n-2), sont les valeurs récursives formule. Donc cette fonction récursive n'est pas difficile à écrire

#includeusing namespace std;
int F(int n)//函数返回一个数对应的Fibonacci数{ if(n0 || n1)//递归边界
return 1; return F(n-1) + F(n-2);//递归公式}
int main(){ //测试
int n; while(cin >> n) cout << F(n) << endl;
return 0;
}

2 La formule récursive de factorielle : n*F(n-1)

La. le code est le suivant :

#includeusing namespace std;
int F(int n){ if(n==0)//递归边界
return 1;
return n*F(n-1);//递归公式}
int main(){ int n; cin >> n; cout << F(n) << endl;
return 0;
}

3. Sommation du tableau

Étant donné un tableau a[]:a[0],a[1],...,a [n-1], comment le résumer de manière récursive ?

Il reste encore deux questions : la limite de récursion et la formule de récursion.

Qu'est-ce que la limite de récursion ? Il n'est pas facile d'y penser pour le moment, mais nous pensons à la sommation. Quel est le processus de sommation de plusieurs nombres ? Quel est le processus de sommation manuelle de x, y, z, w ? Les étapes sont les suivantes :

x+y=a, la tâche devient une sommation a,z,w

a+z=b, la tâche devient une sommation n,w

b+w=c obtient la réponse

Pensez-y, [Obtenez la réponse] Pourquoi pouvez-vous obtenir la réponse à cette étape ? (C'est absurde ?) C'est parce que vous pouvez obtenir la réponse sans ajouter de nombre

Donc, la limite de récursion est qu'il n'y a qu'un seul nombre

Donc, avec la limite de récursion, alors la formule de récursion Drap de laine ? En fait, la formule récursive est implicite dans le processus de calcul manuel :

où + est la somme de deux nombres, et F est la fonction récursive qui trouve la somme de plusieurs nombres. Le code est le suivant :

#includeusing namespace std;
int F(int a[],int start,int end){ if(start==end)//递归边界
return a[start];
return a[start] + F(a,start+1,end);//递归公式}
int main(){ int a[] = {1,2,3,4,5}; int s=0,e=4; cout << F(a,s,e) << endl;
return 0;
}

4. Trouver la valeur maximale d'un élément du tableau

Quel est le processus de recherche manuelle de la valeur maximale, parcours + comparaison, le processus est le suivant :

Par exemple, recherchez 3, 2, 6, valeur maximale de 7, 2, 4 : définissez d'abord la valeur maximale max=-999999, puis comparez les éléments max et du tableau un par un (traverse If a). [i]>max, mettez à jour la valeur de max en a[i], sinon max reste inchangé et continue de reculer jusqu'à la fin du parcours

max<3, puis max=3<🎜. >

max>2, max=3 reste inchangé

max<6, puis max=6

max<7, puis max=7

max>2 , max=7 reste inchangé

max>4, max=7 reste inchangé

La traversée se termine, max=7 est la valeur maximale.

Semblable à la sommation, le La formule récursive est la suivante :

où max est la fonction de plus grande valeur de deux nombres, F est une fonction récursive qui trouve la valeur maximale de plusieurs nombres. Le code est le suivant :

#includeusing namespace std;
#define max(a,b) (a>b?a:b)
int F(int a[],int s,int e){ if(s==e) return a[s]; else if(s+1 == e)//递归边界
return max(a[s],a[e]);
return max(a[s],F(a,s+1,e));//递归公式!!!}
int main(){ int a[] = {5,1,4,6,2}; int s = 0,e = 4; cout << F(a,s,e) << endl;
return 0;
}

. La raison pour laquelle les exemples ci-dessus sont des [exemples simples] est que toutes les récursions ci-dessus appartiennent à une [récursion unidirectionnelle]. Le chemin de la récursion est dans une direction, donc l'idée est relativement facile à penser. 🎜>

Les problèmes de récursion difficiles ne sont généralement pas une récursion à sens unique, mais nécessitent l'utilisation de [backtracking]. La méthode récursive n'est pas facile à penser.

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!