|
récursivité est un concept puissant dans le domaine de l'informatique , mais il peut être difficile pour les débutants à saisir. Récursivité implique une fonction ou méthode elle-même en invoquant à plusieurs reprises dans un contexte différent jusqu'à un contexte « de base » est atteint et retourné. En d'autres termes , pour résoudre un problème , le programme recontexualizes comme un problème légèrement différent . Lors de l'implémentation d'un algorithme récursif , toujours tenir compte de la forme la plus simple du problème et mettre en place cet exemple simplifié comme un « scénario de base », qui toutes les autres versions du problème feront référence . Instructions
1 Définir l'en-tête d'une fonction - le nom de la fonction et de ses entrées. Par exemple, une fonction qui trouve un nombre de Fibonacci particulier peut se présenter comme suit:
fib ( int n) {}
Ici, la fonction calcule le nombre " nième " Fibonacci de la séquence .
2 Notez comment la fonction sera appelée génériquement . Par exemple , lorsque vous appelez fib ( ) , vous devez utiliser un entier comme argument et enregistrer l'entier qu'il calcule :
int result = fib ( x ) ;
3 définir le « scénario de base» de votre problème de récursivité. Il peut y avoir plusieurs cas de base. Comme la séquence de Fibonacci nécessite deux numéros, vous aurez besoin de deux cas de base pour mettre en œuvre sa solution
if ( n == 0) return 0; . If ( n == 1) return 1;
< br > 4 Définir l'étape récursive de votre problème de récursivité comme une version plus petite et plus simple du même problème, référençant l'exemple d'invocation de l'étape 2 . Dans notre exemple, la suite de Fibonacci est une séquence mathématique où chaque numéro de la ligne est la somme des deux nombres précédents dans la séquence . L'algorithme pour trouver un nombre de Fibonacci particulier doit donc se prévaloir deux fois , une fois pour le numéro précédent et une fois pour le numéro avant le numéro précédent :
int result1 = fib ( n-1) ; int result2 = fib ( n-2) ;
retour result1 + result2 ;
5 Mettez la fonction ensemble, par exemple :
fib ( int n) {if ( n == 0) return 0; cas 1else //base if ( n == 1) return 1; //base 2 cas
else {//récursive stepint result1 = fib ( n-1) ; int result2 = fib (n -2);
retour result1 + result2 ;} }
la structure du «scénario de base » et « étape récursive " sera la même pour toutes les fonctions récursives, s'il peut y avoir plusieurs scénarios de référence et les longues étapes récursives .
|
