la récursivité rapport à l'itération

La récursivité est généralement beaucoup plus lent parce que tous les appels de fonction doivent être stockés dans une pile à permettre le retour à la fonction appelante. Dans de nombreux cas, la mémoire doit être allouée et copié à mettre en œuvre isolation du périmètre.

Quelques optimisations, comme la queue d'appel d'optimisation, faire des récurrences plus rapide, mais ce n'est pas toujours possible, et ne sont pas mis en œuvre dans toutes les langues.

Les principales raisons d'utiliser la récursivité sont

• qu'il est plus intuitif dans beaucoup de cas, quand il imite notre approche du problème
• que certaines structures de données comme les arbres sont plus faciles à étudier l'utilisation de la récursivité (ou aurait besoin de piles en tout cas)

Bien sûr, chaque récursion peut être modélisé comme une sorte de boucle : c'est que le CPU en fin de compte ne. Et la récursivité lui-même, plus directement, les moyens de mettre les appels de fonction et les étendues dans une pile. Mais les changements d'algorithme récursif d'une boucle on pourrait avoir besoin de beaucoup de travail et de rendre votre code moins maintenable : comme pour chaque optimisation, il ne devrait être envisagée que lorsque certains profils ou des éléments de preuve ont montré qu'il est nécessaire.

Question :

Et si la récursivité est généralement plus lent, ce qui est la raison technique pour toujours à l'aide de plus de pour tour de boucle?

Réponse :

Parce que, dans certains algorithmes sont difficiles à résoudre de manière itérative. Essayez de résoudre la profondeur de recherche est à la fois de manière récursive et itérative. Vous obtiendrez l'idée qu'il est clair difficiles à résoudre DFS avec itération.

Une autre bonne chose à essayer : Essayer d'écrire de Fusion de tri de manière itérative. Il vous faudra très peu de temps.

Question :

Est-il correct de dire que partout, la récursivité est utilisé pour la boucle pourrait être utilisé?

Réponse :

Oui. Cette fil a une très bonne réponse à cette question.

Question :

Et si il est toujours possible de convertir une récursion dans une boucle for est là une règle de pouce moyen de le faire?

Réponse :

Confiance en moi. Essayez d'écrire votre propre version de résoudre en profondeur d'abord de recherche de manière itérative. Vous remarquerez que certains problèmes sont plus faciles à résoudre de manière récursive.

Conseil : la Récursivité est bon quand vous êtes à la résolution d'un problème qui peut être résolu par diviser pour régner technique.

D'écrire une méthode équivalente à l'aide de l'itération, nous devons explicitement l'utilisation d'une pile. Le fait que l'itératif version nécessite une pile pour sa solution indique que le problème est assez difficile qu'il puisse bénéficier de la récursivité. En règle générale, la récursivité est le plus approprié pour des problèmes qui ne peuvent être résolus par un montant fixe de la mémoire et, par conséquent, nécessitent une pile lorsque résolu de manière itérative.
Cela dit, la récursivité et itération peut montrer le même résultat, tandis qu'ils suivent de modèle différent.Pour décider de la méthode qui fonctionne le mieux est au cas par cas et de bonnes pratiques est à choisir en fonction sur le même schéma que le problème de la façon suivante.

Par exemple, pour trouver le n-ième nombre triangulaire de
Triangulaire de la séquence: 1 3 6 10 15 ...
Un programme qui utilise un algorithme itératif pour trouver le n-ième nombre triangulaire:

À l'aide d'un algorithme itératif:

//Triangular.java
import java.util.*;
class Triangular {
   public static int iterativeTriangular(int n) {
      int sum = 0;
      for (int i = 1; i <= n; i ++)
         sum += i;
      return sum;
   }
   public static void main(String args[]) {
      Scanner stdin = new Scanner(System.in);
      System.out.print("Please enter a number: ");
      int n = stdin.nextInt();
      System.out.println("The " + n + "-th triangular number is: " + 
                            iterativeTriangular(n));
   }
}//enter code here

À l'aide d'un algorithme récursif:

//Triangular.java
import java.util.*;
class Triangular {
   public static int recursiveTriangular(int n) {
      if (n == 1)
     return 1;  
      return recursiveTriangular(n-1) + n; 
   }

   public static void main(String args[]) {
      Scanner stdin = new Scanner(System.in);
      System.out.print("Please enter a number: ");
      int n = stdin.nextInt();
      System.out.println("The " + n + "-th triangular number is: " + 
                             recursiveTriangular(n)); 
   }
}

Je crois me souvenir de mon professeur d'informatique-dire à l'époque que tous les problèmes qui ont récursive des solutions ont également itératif des solutions. Il dit que une solution récursive est généralement plus lent, mais ils sont fréquemment utilisés quand ils sont plus faciles à comprendre et que le code itératif solutions.

Toutefois, dans les cas les plus avancés, récursive des solutions, je ne crois pas qu'il sera toujours en mesure de les mettre en œuvre à l'aide d'un simple for boucle.

Beaucoup de bonnes raisons ont été données et je voudrais partager un point de plus. Certains des problèmes sont magnifiquement résolu par récurrence plutôt ne peut être résolu que par la récursivité. Un échantillon de exemple serait:

Imprimer toutes les valeurs d'un tableau, mais les éléments d'un tableau peut être des tableaux ainsi. Il pourrait y avoir des tableaux imbriqués, mais nous ne sommes pas sûr de la profondeur de tableaux imbriqués.

Une belle solution serait celui-ci:

<?php
  function print_all_items($array){

       foreach($array as $key=>$value){
           if(is_array($value)) { 
             print_all_items($value);
           }
           else{
             echo "$key => $value <br/>";
           }
       }
  }

$array = array("first" => "first value",  
              "second" => "second value",  
              "third" => "third value",  
               "fourth"=>array(1,2,3,4,5),
              "fifth"=>array(
                       "second array 1",
                       "second array 2",
                       "second array 3",
                       array(
                           "third array 1",
                           "third array 2",
                           "third array 3",
                           )
                       ),
              );

print_all_items($array);

De sortie:

first => first value 
second => second value 
third => third value 
0 => 1 
1 => 2 
2 => 3 
3 => 4 
4 => 5 
0 => second array 1 
1 => second array 2 
2 => second array 3 
0 => third array 1 
1 => third array 2 
2 => third array 3 

Maintenant ce type de problème ne peut être résolu par iterative approach puisque la nature des problèmes exige solution dynamique.

Réponse courte: le compromis est la récursivité est plus rapide et pour les boucles de prendre moins de mémoire, dans presque tous les cas. Cependant, il existe généralement des moyens de changer la boucle for ou la récursivité pour le faire fonctionner plus rapidement