Qu'est-ce que la récursivité et quand dois-je utiliser?

Il y a un certain nombre de bonnes explications de la récursivité dans ce fil, cette réponse, c'est pourquoi vous ne devriez pas l'utiliser dans la plupart des langues.* Dans la plupart des grandes impératif implémentations de langue (c'est à dire tous les grands de la mise en œuvre de C, C++, Basic, Python, Ruby,Java et C#) itération est infiniment préférable à la récursivité.

De voir pourquoi, marcher à travers les étapes que ci-dessus langues à utiliser pour l'appel d'une fonction:

1. espace est taillé sur la pile pour les arguments de la fonction et les variables locales
2. les arguments de la fonction sont copiés dans ce nouvel espace
3. de contrôle des sauts de la fonction
4. le code de fonction s'exécute
5. le résultat de la fonction est copié dans une valeur de retour
6. la pile est remonté à sa position précédente
7. de contrôle revient à l'endroit où la fonction a été appelée

De faire toutes ces étapes prennent du temps, généralement un peu plus qu'il n'en faut pour parcourir une boucle. Cependant, le vrai problème est dans l'étape #1. Lorsque de nombreux programmes de démarrage, ils assignent un seul morceau de la mémoire de leur pile, et quand ils sont à court de mémoire (souvent, mais pas toujours en raison de la récursivité), le programme se bloque à cause d'un un débordement de pile.

Donc, dans ces langues, la récursivité est plus lent, et il vous rend vulnérable à s'écraser. Il y a encore quelques arguments pour l'utilisant bien. En général, le code écrit de manière récursive est plus courte et un peu plus élégante, une fois que vous savez comment faire pour le lire.

Il y a une technique que la langue exécutants peuvent utiliser appelée la queue d'appel d'optimisation qui peut éliminer certaines classes de débordement de la pile. Mettre succinctement: si une fonction de retour d'expression est simplement le résultat d'un appel de fonction, alors vous n'avez pas besoin d'ajouter un nouveau niveau dans la pile, vous pouvez les réutiliser pour la fonction appelée. Malheureusement, peu de langage impératif-implémentations de queue-appel d'optimisation intégré.

* J'aime la récursivité. Mon préféré statique de la langue ne pas utiliser de boucles à tous, la récursivité est la seule façon de faire quelque chose à plusieurs reprises. Je ne pense pas que la récursivité est généralement une bonne idée dans des langues qui ne sont pas à l'écoute pour elle.

** Par la voie de Mario, le nom typique pour votre ArrangeString fonction "joindre", et je serais surpris si la langue de votre choix n'a pas déjà une.

A la base, l'informatique sens, la récursivité est une fonction qui s'appelle elle-même. Disons que vous avez une liste liée à la structure:

struct Node {
    Node* next;
};

Et vous voulez savoir combien de temps une liste chaînée est que vous pouvez faire cela avec la récursivité:

int length(const Node* list) {
    if (!list->next) {
        return 1;
    } else {
        return 1 + length(list->next);
    }
}

(Ceci pourrait être fait avec une boucle for, mais est utile comme une illustration de la notion)

La récursivité est une méthode de résolution de problèmes basée sur la division et de conquête de la mentalité.
L'idée de base est que vous prenez le problème d'origine et de le diviser en plus petites (plus facilement résolu) instances de lui-même, de résoudre ces petites instances (habituellement en utilisant le même algorithme de nouveau), puis remonter vers la solution finale.

L'exemple canonique est une routine pour générer la Factorielle de n. La Factorielle de n est calculé en multipliant tous les nombres entre 1 et n. Une solution itérative en C# ressemble à ceci:

public int Fact(int n)
{
  int fact = 1;

  for( int i = 2; i <= n; i++)
  {
    fact = fact * i;
  }

  return fact;
}

Il n'y a rien de surprenant au sujet de la solution itérative et il doit faire sens pour quiconque est familier avec le C#.

La solution récursive est trouvé en reconnaissant que le nième Factorielle est n * Fact(n-1). Ou pour le dire d'une autre façon, si vous savez ce que la Factorielle du nombre est, vous pouvez calculer la suivante. Voici la solution récursive en C#:

public int FactRec(int n)
{
  if( n < 2 )
  {
    return 1;
  }

  return n * FactRec( n - 1 );
}

La première partie de cette fonction est connue comme une de la Base de Cas (ou parfois de la Garde de la Clause) et tout ce qui empêche l'algorithme de running à tout jamais. Elle retourne la valeur 1 lorsque la fonction est appelée avec une valeur de 1 ou moins. La deuxième partie est plus intéressante et est connu comme le Récursive Étape. Ici, nous appelons la même méthode avec un peu modifié le paramètre (nous décrémenter par 1), puis multiplier le résultat avec notre copie de n.

Lors de la première rencontre, ce peut être une sorte de confusion, donc il est instructif d'examiner comment il fonctionne lorsque vous exécutez. Imaginez que nous appelons FactRec(5). Nous entrons dans la routine, ne sont pas récupérés par le cas de base et on se retrouve donc comme ceci:

//In FactRec(5)
return 5 * FactRec( 5 - 1 );

//which is
return 5 * FactRec(4);

Si nous re-entrer dans la méthode avec le paramètre 4 nous sommes de nouveau n'est pas stoppé par le gardien de la clause et donc nous retrouver à:

//In FactRec(4)
return 4 * FactRec(3);

Si l'on substitue cette valeur de retour dans la valeur de retour ci-dessus nous obtenons

//In FactRec(5)
return 5 * (4 * FactRec(3));

Cela devrait vous donner une idée de la façon dont la solution finale est arrivé au nous allons donc la voie rapide et montrer à chaque étape sur le chemin vers le bas:

return 5 * (4 * FactRec(3));
return 5 * (4 * (3 * FactRec(2)));
return 5 * (4 * (3 * (2 * FactRec(1))));
return 5 * (4 * (3 * (2 * (1))));

Finale de substitution se produit lorsque le cas de base est déclenchée. À ce stade, nous avons une simple algrebraic formule pour résoudre qui correspond directement à la définition des Factorielles, en premier lieu.

Il est instructif de noter que chaque appel à la méthode les résultats dans une base de cas a été déclenché ou un appel à la même méthode, où les paramètres sont plus proches d'une base de cas (souvent appelé un appel récursif). Si ce n'est pas le cas, alors la méthode s'exécute indéfiniment.

La récursivité se réfère à une méthode qui permet de résoudre un problème par la résolution d'une version plus petite de la le problème et puis en utilisant le résultat de plus quelques autres le calcul de formuler la réponse au problème initial. Souvent, dans le processus de résolution de la plus petite version, la méthode permettra de résoudre une encore plus petite version du problème, et ainsi de suite, jusqu'à ce qu'il atteigne un "cas de base" qui est trivial à résoudre.

Par exemple, pour calculer une factorielle du nombre X, on peut la représenter comme X times the factorial of X-1. Ainsi, la méthode "analyse" pour trouver la factorielle de X-1, et multiplie ensuite ce qu'il a obtenu par X de donner une réponse définitive. Bien sûr, de trouver la factorielle de X-1, il va d'abord calculer la factorielle de X-2, et ainsi de suite. Le cas de base serait quand X est 0 ou 1, dans lequel cas, il sait que le retour 1 depuis 0! = 1! = 1.

1. Une fonction qui s'appelle elle-même
2. Lorsqu'une fonction peut être (facilement) décomposé en une simple opération de plus la même fonction sur certains plus petite partie du problème. Devrais-je dire, plutôt, que cela en fait un bon candidat pour la récursivité.
3. Ils ne!

L'exemple canonique est la factorielle qui ressemble à:

int fact(int a) 
{
  if(a==1)
    return 1;

  return a*fact(a-1);
}

En général, la récursivité n'est pas nécessairement rapide (appel de fonction, les frais généraux tend à être élevée en raison des fonctions récursives ont tendance à être de petite taille, voir ci-dessus) et peuvent souffrir de certains problèmes (débordement de pile quelqu'un?). Certains disent qu'ils ont tendance à être difficile à obtenir dans non négligeable de cas, mais je n'ai pas vraiment acheter que. Dans certaines situations, la récursivité fait le plus de sens et est la plus élégante et la plus claire de la façon d'écrire une fonction particulière. Il convient de noter que certaines langues faveur récursive des solutions et de les optimiser beaucoup plus (LISP vient à l'esprit).

La récursivité est une expression directement ou indirectement de référencement de lui-même.

Envisager acronymes récursifs comme un simple exemple:

• GNU signifie GNU n'est Pas Unix
• PHP signifie PHP: Hypertext Preprocessor
• YAML signifie YAML Ain't Markup Language
• VIN signifie Vin n'Est Pas un Émulateur
• VISA signifie de Visa International Service Association

Plus d'exemples sur Wikipedia

Récursive de déclaration est celle qui vous permet de définir le processus de quoi faire la prochaine que d'une combinaison d'entrées et de ce que vous avez déjà fait.

Par exemple, prendre factorielle:

factorial(6) = 6*5*4*3*2*1

Mais il est facile de voir factorielle(6) est aussi:

6 * factorial(5) = 6*(5*4*3*2*1).

Donc généralement:

factorial(n) = n*factorial(n-1)

Bien sûr, la chose la plus délicate à propos de la récursivité, c'est que si vous voulez définir les choses en termes de ce que vous avez déjà fait, il doit être un endroit pour commencer.

Dans cet exemple, nous venons de faire un cas particulier par la définition de la factorielle(1) = 1.

Maintenant, nous voyons de bas en haut:

factorial(6) = 6*factorial(5)
                   = 6*5*factorial(4)
                   = 6*5*4*factorial(3) = 6*5*4*3*factorial(2) = 6*5*4*3*2*factorial(1) = 6*5*4*3*2*1

Depuis que nous avons défini factorielle(1) = 1, nous atteignons le "bas".

En règle générale, les procédures récursives sont en deux parties:

1) La partie récursive, qui définit une procédure en termes de nouvelles entrées combinées avec ce que vous avez "déjà fait" par la même procédure. (c'est à dire factorial(n) = n*factorial(n-1))

2) Une pièce de base, ce qui permet de s'assurer que le processus ne soit pas répéter éternellement en lui donnant un peu de place pour le début (c'est à dire factorial(1) = 1)

Il peut être un peu déroutant pour obtenir autour de votre tête au premier abord, mais il suffit de regarder un tas d'exemples et il devrait tous se réunir. Si vous voulez une compréhension beaucoup plus profonde de la notion, étude induction mathématique. Aussi, soyez conscient que certaines langues optimiser les appels récursifs, tandis que d'autres ne le font pas. Il est assez facile de faire incroyablement lent fonctions récursives si vous n'êtes pas prudent, mais il existe également des techniques pour les rendre performants dans la plupart des cas.

Espère que cela aide...

1.)
Une méthode est récursive si elle peut s'appeler elle-même; soit directement:

void f() {
   ... f() ... 
}

ou indirectement:

void f() {
    ... g() ...
}

void g() {
   ... f() ...
}

2.) Lors de l'utilisation de la récursivité

Q: Does using recursion usually make your code faster? 
A: No.
Q: Does using recursion usually use less memory? 
A: No.
Q: Then why use recursion? 
A: It sometimes makes your code much simpler!

3.) Les gens utiliser la récursivité seulement quand il est très complexe à écrire du code itératif. Par exemple, l'arbre transversal des techniques comme la précommande, postorder peut être fait à la fois itérative et récursive. Mais habituellement, nous utilisons récursive en raison de sa simplicité.

Bien, c'est un assez décent définition que vous avez. Et wikipédia a une bonne définition trop. Donc, je vais ajouter un autre (probablement le pire) de la définition pour vous.

Quand les gens parlent de "récursivité", ils sont généralement de parler d'une fonction qu'ils ont écrit qui s'appelle elle-même à plusieurs reprises jusqu'à ce qu'il se fait de son travail. La récursivité peut être utile lors de la traversée des hiérarchies dans des structures de données.

Répéter sur un problème résolu: ne rien faire, vous avez terminé.

Répéter sur un problème ouvert: faire la prochaine étape, puis répéter sur le reste.

Une fonction récursive est une fonction qui contient un appel à elle-même. Un appel récursif struct est une structure qui contient une instance de lui-même. Vous pouvez combiner les deux, comme un appel récursif de la classe. La partie clé de l'récursive de l'élément, c'est qu'il contient une instance/appel de lui-même.

Tenir compte de deux miroirs face à face. Nous avons vu le pur effet infini qu'ils font. Chaque réflexion est une instance d'un miroir, qui est contenue dans une autre instance d'un miroir, etc. Le miroir contenant un reflet de lui-même est la récursivité.

Un un arbre de recherche binaire est un bon exemple de programmation de la récursivité. La structure est récursive à chaque Nœud contenant 2 instances d'un Nœud. Fonctions pour travailler sur un arbre de recherche binaires sont également récursive.

Vous voulez l'utiliser à tout moment vous avez une structure en arbre. Il est très utile pour lire des données XML.

"Si j'ai un marteau, faire tout ce qui ressemble à un clou."

La récursivité est un problème de résolution de stratégie pour énorme de problèmes, où à chaque pas, juste de, "la tour 2 petites choses dans un plus grand chose," à chaque fois avec le même marteau.

Exemple

Supposons que votre bureau est couvert avec un désordre désorganisé de 1024 papiers. Comment voulez-vous faire un soigné, propre pile de papiers à partir du désordre, en utilisant la récursivité?

1. Diviser: Propagation de toutes les feuilles, si vous avez juste une feuille dans chaque pile.
2. Conquer:
   1. Aller autour, de placer chaque feuille par-dessus une autre feuille. Vous avez maintenant des piles de 2.
   2. Aller autour de, mettre tous les 2 de la pile sur le dessus de l'autre 2-de la pile. Vous avez maintenant des piles de 4.
   3. En faire le tour, en plaçant chaque 4-pile sur le dessus de l'autre 4-pile. Vous avez maintenant des piles de 8.
   4. ... et encore ...
   5. Vous avez maintenant une énorme pile de 1024 feuilles!

Avis que c'est assez intuitif, en dehors de tout compter (ce qui n'est pas strictement nécessaire). Vous ne pourriez pas aller tout le chemin vers le bas pour 1 feuille de meules, dans la réalité, mais vous pourrait, et il fonctionne encore. L'important, c'est le marteau: Avec vos bras, vous pouvez toujours mettre une pile au-dessus de l'autre pour faire un plus gros stack, et il n'a pas d'importance (dans la raison) quel soit pile est.

hey, désolé si mon avis est d'accord avec quelqu'un, j'essaie juste d'expliquer la récursivité dans la plaine de l'anglais.

supposons que vous disposez de trois gestionnaires - Jack, John et Morgan.
Jack gère 2 programmeurs, John - 3, et Morgan - 5.
vous allez donner à chaque gestionnaire de 300$ et que vous voulez savoir quel serait le coût.
La réponse est évidente - mais si de 2 de Morgan-s employés sont aussi des gestionnaires?

VOICI la récursivité.
vous commencez par le haut de la hiérarchie. la estival coût est de 0$.
vous commencez avec Jack,
Ensuite vérifier s'il a toute les gestionnaires que les employés. si vous trouvez l'un d'eux sont, de vérifier si elles ont toute les gestionnaires que les employés, et ainsi de suite. Ajouter 300$ à la estival coût à chaque fois que vous trouver un gestionnaire.
lorsque vous avez terminé avec Jack, allez à la de Jean, ses employés, et de Morgan.

Vous ne saurez jamais, combien de cycles allez-vous avant d'obtenir une réponse, si vous savez comment beaucoup de gestionnaires vous avez et combien de Budget pouvez-vous dépenser.

La récursivité est un arbre avec des branches et des feuilles, appelé les parents et les enfants, respectivement.
Lorsque vous utilisez une récursivité de l'algorithme, plus ou moins consciemment de construire un arbre à partir des données.

De l'algorithme expositions structurels la récursivité sur un type de données si, fondamentalement, se compose d'un interrupteur de mise en rapport avec des cas pour chaque cas le type de données.

par exemple, lorsque vous travaillez sur un type

  tree = null 
       | leaf(value:integer) 
       | node(left: tree, right:tree)

structurelle de l'algorithme récursif aurait la forme

 function computeSomething(x : tree) =
   if x is null: base case
   if x is leaf: do something with x.value
   if x is node: do something with x.left,
                 do something with x.right,
                 combine the results

c'est vraiment le moyen le plus évident d'écrire des algorith qui fonctionne sur une structure de données.

maintenant, quand vous regardez les entiers (ainsi, les nombres naturels), tel que défini à l'aide des axiomes de Peano,

 integer = 0 | succ(integer)

vous voyez que structurelle de l'algorithme récursif sur des entiers ressemble à ceci

 function computeSomething(x : integer) =
   if x is 0 : base case
   if x is succ(prev) : do something with prev

le trop-bien-connu fonction factorielle est le plus trivial exemple de
ce formulaire.

La récursivité en informatique est une technique utilisée pour calculer un résultat ou un effet secondaire normal de retour à partir d'une seule fonction (méthode, la procédure, ou bloc) de l'invocation.

La fonction récursive, par définition, doivent avoir la capacité de s'appeler elle-même, soit directement ou indirectement (par le biais d'autres fonctions) en fonction d'une condition de sortie ou les conditions n'étant pas remplies. Si une sortie condition est remplie, le particulier invocation retourne à l'appelant. Cela continue jusqu'à la première invocation est retourné à partir de, date à laquelle le résultat souhaité ou d'effet secondaire sera disponible.

Comme un exemple, voici une fonction pour effectuer l'algorithme Quicksort en Scala (copiés de l'article de Wikipédia pour Scala)

def qsort: List[Int] => List[Int] = {
  case Nil => Nil
  case pivot :: tail =>
    val (smaller, rest) = tail.partition(_ < pivot)
    qsort(smaller) ::: pivot :: qsort(rest)
}

Dans ce cas, la condition de sortie est une liste vide.

La récursivité, c'est quand vous avez une opération qui utilise lui-même. Il en sera probablement de disposer d'un point d'arrêt, sinon il serait à tout jamais.

Disons que vous souhaitez rechercher un mot dans le dictionnaire. Vous avez une opération appelée "look-up" à votre disposition.

Votre ami dit "j'ai vraiment pu cuillère sur certains pudding dès maintenant!" Vous ne savez pas ce qu'il veut dire, si vous regardez en haut "cuillère" dans le dictionnaire, et il lit quelque chose comme ceci:

Cuillère: nom - un ustensile avec un tour scoop à la fin.
Cuillère: verbe à l'aide d'une cuillère sur quelque chose
Cuillère: verbe - se blottir près de derrière

Aujourd'hui, que vous n'êtes vraiment pas bien l'anglais, cela vous mène dans la bonne direction, mais vous avez besoin de plus d'infos. Si vous sélectionnez "ustensile" et "câlin" pour plus d'informations.

Des câlins: verbe - pour se blottir
Ustensile: nom - un outil, souvent de manger un ustensile

Hey! Vous savez ce qui se est, et il n'a rien à voir avec le pudding. Vous savez aussi que le pudding est quelque chose que vous mangez, si elle fait sens aujourd'hui. Votre ami doit avoir envie de manger du pudding avec une cuillère.

Okay, Okay, c'était un très boiteux exemple, mais il illustre (peut-être mal) les deux parties principales de la récursivité.
1) Il utilise lui-même. Dans cet exemple, vous n'avez pas vraiment l'air d'un mot de façon significative jusqu'à ce que vous comprenez, et que peut signifier plus de mots. Ce qui nous amène au point deux,
2) Il s'arrête quelque part. Il doit avoir une sorte de cas de base. Sinon, vous auriez simplement une recherche de chaque mot dans le dictionnaire, qui n'est probablement pas trop utile. Notre scénario de base est que vous avez obtenu suffisamment d'informations pour faire un lien entre ce que vous l'avez déjà fait et de ne pas comprendre.

Traditionnels exemple qui est donné est factoriel, où 5 factorielle est 1*2*3*4*5 (120). Le cas de base serait de 0 (ou 1, selon le cas). Donc, pour tout nombre entier n, vous effectuez les opérations suivantes

est n égal à 0? retour 1
sinon, retour n * (factorielle de n-1)

nous allons faire cela avec l'exemple de 4 (dont on sait à l'avance est 1*2*3*4 = 24).

la factorielle de 4 ... est-il 0? non, donc il doit être 4 * factorielle de 3
mais quelle est la factorielle de 3? c'est 3 * factorielle de 2
la factorielle de 2 est 2 * factorielle de 1
la factorielle de 1 est 1 * factorielle de 0
et nous SAVONS que la factorielle de 0! 😀 c'est 1, c'est la définition
la factorielle de 1 est 1 * factorielle de 0, qui était de 1... donc 1*1 = 1
la factorielle de 2 est 2 * factorielle de 1, qui était de 1... donc 2*1 = 2
la factorielle de 3 est 3 * factorielle de 2, qui a été 2... donc 3*2 = 6
la factorielle de 4 (enfin!!) est 4 * factorielle de 3, 6... 4*6 est de 24

Factorielle est un simple cas de "cas de base, et utilise lui-même".

Maintenant, remarquez, nous étions encore à travailler sur la factorielle de 4 tout le chemin vers le bas... Si nous voulions factorielle de 100, nous devrions avoir à aller tout le chemin jusqu'à 0... ce qui pourrait avoir beaucoup de frais généraux à elle. De la même manière, si nous trouvons un obscur mot à chercher dans le dictionnaire, il pourrait prendre, à la recherche d'autres mots et de numérisation pour le contexte des indices jusqu'à ce que nous trouver un lien, nous sommes familiers avec. Récursive méthodes peuvent prendre beaucoup de temps pour travailler leur chemin à travers. Cependant, quand ils sont utilisés correctement, et compris, ils peuvent faire le travail compliqué étonnamment simple.

La récursivité est une technique de définition d'une fonction, d'un ensemble ou d'un algorithme en fonction d'elle-même.

Par exemple

n! = n(n-1)(n-2)(n-3)...........*3*2*1

Maintenant elle peut être définie de manière récursive comme:-

n! = n(n-1)!   for n>=1

En termes de programmation, lorsqu'une fonction ou méthode s'appelle elle-même à plusieurs reprises, jusqu'à ce qu'une condition spécifique devient satisfait, ce processus est appelé la Récursivité. Mais il doit y avoir une condition d'arrêt et de la fonction ou de la méthode doit pas entrer dans une boucle infinie.

J'ai créé une fonction récursive pour concaténer une liste de chaînes de caractères, avec un séparateur entre eux. Je l'utilise principalement pour créer des expressions SQL, en passant par une liste de champs comme le "éléments "et un" virgule+espace' comme séparateur. Voici la fonction (Elle utilise Borland Builder types de données natifs, mais peut être adapté à toutes les autres de l'environnement):

String ArrangeString(TStringList* items, int position, String separator)
{
  String result;

  result = items->Strings[position];

  if (position <= items->Count)
    result += separator + ArrangeString(items, position + 1, separator);

  return result;
}

J'appelle cela de cette façon:

String columnsList;
columnsList = ArrangeString(columns, 0, ", ");

Imaginez que vous avez un tableau nommé "champs " avec ces données à l'intérieur: 'albumName', 'releaseDate', 'labelId'. Vous pouvez ensuite appeler la fonction:

ArrangeString(fields, 0, ", ");

Que la fonction commence à travailler, la variable "résultat "reçoit la valeur de la position 0 de la matrice, ce qui est" albumName'.

Puis il vérifie si la position de l'affaire est la dernière. Comme il n'est pas le cas, il concatène le résultat avec le séparateur et le résultat d'une fonction, qui, oh mon Dieu, est-ce la même fonction. Mais cette fois, check it out, il appelle lui-même en ajoutant 1 à la position.

ArrangeString(fields, 1, ", ");

Il ne cesse de répéter, de la création d'une pile LIFO, jusqu'à ce qu'il atteigne un point où la position en cours EST la dernière, alors la fonction retourne uniquement le point sur cette position sur la liste, pas de la concaténation de plus. Ensuite la pile est concaténé à l'envers.

Eu? Si vous ne le faites pas, j'ai une autre façon de l'expliquer. :o)

Mario, je ne comprends pas pourquoi vous avez utilisé la récursivité pour l'exemple.. Pourquoi ne pas simplement faire une boucle par chaque entrée? Quelque chose comme ceci:

String ArrangeString(TStringList* items, String separator)
{
    String result = items->Strings[0];

    for (int position=1; position < items->count; position++) {
        result += separator + items->Strings[position];
    }

    return result;
}

La méthode ci-dessus serait plus rapide et plus simple. Il n'y a pas besoin d'utiliser la récursivité en place d'une boucle simple. Je pense que ces sortes d'exemples est pourquoi la récursivité obtient une mauvaise réputation. Même les canonique de la fonction factorielle exemple est mieux mis en œuvre avec une boucle.