Explication détaillée de l'algorithme récursif Java (disposition des nœuds de puissance)

L'algorithme

JavaRecursive est un algorithme récursif implémenté sur la base du langage Java. Les algorithmes récursifs sont efficaces pour résoudre une large classe de problèmes, ce qui rend l'algorithme concis et facile à comprendre. Ensuite, cet article vous présentera les connaissances sur les algorithmes récursifs Java. Les amis intéressés peuvent apprendre ensemble

Un algorithme récursif est un algorithme qui appelle directement ou indirectement ses propres fonctions ou. méthodes. L'algorithme récursif Java est un algorithme récursif implémenté sur la base du langage Java. L'essence de l'algorithme récursif est de décomposer le problème en sous-problèmes du même type, de taille réduite, puis d'appeler des méthodes de manière récursive pour représenter la solution au problème. Les algorithmes récursifs sont efficaces pour résoudre une large classe de problèmes, ce qui rend l'algorithme concis et facile à comprendre.

Les caractéristiques de l'algorithme récursif dans la résolution de problèmes :

1) La récursivité s'appelle elle-même dans la méthode.

2) Lors de l'utilisation de la stratégie de récursion incrémentale, il doit y avoir une condition de fin de récursion claire, appelée sortie de récursion.

3) La résolution de problèmes par algorithmes récursifs semble généralement très simple, mais l'efficacité opérationnelle de la résolution de problèmes par algorithmes récursifs est faible. Par conséquent, il n’est généralement pas recommandé d’utiliser des algorithmes récursifs pour concevoir des programmes.

4) Pendant le processus d'appel récursif, le système ouvre une pile pour stocker les points de retour, les quantités locales, etc. Trop de récursions peuvent facilement provoquer un débordement de pile, etc. Par conséquent, il n'est généralement pas recommandé d'utiliser des algorithmes récursifs pour concevoir des programmes.

　La « répétition » incorporée dans l'algorithme récursif a généralement trois exigences :

Premièrement, chaque appel est réduit en échelle (généralement réduit de moitié) ;

La seconde est qu'il existe un lien étroit entre deux répétitions adjacentes, et la précédente doit être préparée pour la suivante (généralement la sortie de la précédente est utilisée comme entrée de la suivante) ;

Troisièmement, lorsque l'échelle du problème est extrêmement petite, la solution doit être donnée directement au lieu d'appels récursifs. Par conséquent, chaque appel récursif est conditionnel (à condition que l'échelle n'atteigne pas la taille du direct. réponse), et récursion inconditionnelle L'appel deviendra uneboucle morte et ne pourra pas se terminer normalement.

Afin de comprendre l'algorithme récursif, voici un exemple comme suit :

Description du problème :

Résoudre le Numéro de séquence de Fibonacci La valeur de 10 positions ? (Séquence de Fibonacci, également connue sous le nom de Séquence du nombre d'or, fait référence à une telle séquence : 1, 1, 2, 3, 5, 8, 13, 21. ...En mathématiques , la séquence de Fibonacci est définie récursivement comme suit : F0=0, F1=1, Fn=F(n-1)+F(n-2) (n>=2 , n∈N*))

Liste de codes Java :

package com.bjpowernode.test; 
 
 public classFab { 
 
 public static void main(String args[]){ 
 System.out.println(fab(5)); 
 } 
 private static int fab(int index){ 
 if(index==1 || index==2){ 
  return 1; 
 }else{ 
  return fab(index-1)+fab(index-2); 
 } 
 } 
 }

Analyse du programme :

Cet exemple est un exemple très classique, principalement La séquence de Fibonacci est implémentée par récursivité. La sortie de cet algorithme récursif se trouve dans le segment de code

 if(index==1 || index==2){ 
 return 1; 
 }

Si l'index du programme remplit les conditions, la récursion s'arrêtera. Le processus d'exécution de ce programme est donc :

Jusqu'à ce stade de l'analyse du programme, la mise en œuvre récursive est terminée. Les lecteurs peuvent simplement faire une démo pour avoir une idée. cet algorithme. La subtilité, en fait, beaucoup de gens disent que les algorithmes sont difficiles et difficiles à atteindre. En fait, maîtriser la racine de l'algorithme est le plus important. Quelle est la racine de l'algorithme ? à titre d'exemple, je pense que cette racine est cette sortie, tant que vous trouvez la sortie, l'algorithme se mettra naturellement en place.

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!