Comprendre comment fonctionnent les fonctions récursives

1.La fonction est appelée récursivement jusqu'à ce qu'une condition est remplie. Cette condition est a > b. Lorsque cette condition est remplie, retourner 0. À première vue, je m'attendrais à ce que la valeur de retour soit 0, ce qui est évidemment incorrect.

Voici ce que l'Informatique Informatique sumInts(2,5) penserait s'il était capable de:

I want to compute sumInts(2, 5)
for this, I need to compute sumInts(3, 5)
and add 2 to the result.
  I want to compute sumInts(3, 5)
  for this, I need to compute sumInts(4, 5)
  and add 3 to the result.
    I want to compute sumInts(4, 5)
    for this, I need to compute sumInts(5, 5)
    and add 4 to the result.
      I want to compute sumInts(5, 5)
      for this, I need to compute sumInts(6, 5)
      and add 5 to the result.
        I want to compute sumInts(6, 5)
        since 6 > 5, this is zero.
      The computation yielded 0, therefore I shall return 5 = 5 + 0.
    The computation yielded 5, therefore I shall return 9 = 4 + 5.
  The computation yielded 9, therefore I shall return 12 = 3 + 9.
The computation yielded 12, therefore I shall return 14 = 2 + 12.

Comme vous le voyez, un appel à la fonction sumInts renvoie réellement 0 mais ce n'est pas la valeur finale car l'ordinateur doit toujours ajouter 5 à ce 0, puis 4 à la résultat, puis 3, puis 2, comme décrit par les quatre dernières phrases des pensées de notre ordinateur. Notez que dans la récursivité, l'ordinateur ne doit pas seulement calculer l'appel récursif, il doit également se rappeler quoi faire avec la valeur renvoyée par l'appel récursif. Il y a une zone spéciale de la mémoire de l'ordinateur appelée la pile où ce type d'information est enregistré, cet espace est limité et les fonctions trop récursives peuvent épuiser la pile: c'est la pile overflow donne son nom à notre site le plus aimé.

Votre déclaration semble faire l'hypothèse implicite que l'ordinateur oublie ce qu'il était lors d'un appel récursif, mais ce n'est pas le cas, c'est pourquoi votre conclusion ne correspond pas à votre observation.

2.L'impression de la valeur de 'a' à chaque itération donne une valeur que j'attends: 2, 3, 4, 5 (à quel point 5 + 1 > b qui répond à la première condition: a > b) mais je ne vois toujours pas comment la valeur de 14 est atteindre.

C'est parce que la valeur de retour n'est pas un a lui-même, mais la somme de la valeur de a et la valeur retournée par l'appel récursif.

Pour comprendre la récursivité, vous devez penser le problème d'une manière différente. Au lieu d'une grande séquence logique d'étapes qui a du sens dans son ensemble, vous prenez plutôt un gros problème et divisez-le en petits problèmes et résolvez-les, une fois que vous avez une réponse aux sous-problèmes, vous combinez les résultats des sous-problèmes pour résoudre le plus gros problème. Pensez à vous et à vos amis qui ont besoin de compter le nombre de billes dans un énorme seau. Vous prenez chacun un seau plus petit et aller compter ceux individuellement et lorsque vous avez terminé, vous ajoutez les totaux d'ensemble.. Eh bien maintenant, si chacun d'entre vous trouve un ami et divise les seaux plus loin, alors vous avez juste besoin d'attendre que ces autres amis pour comprendre leurs totaux, le ramener à chacun d'entre vous, vous l'additionnez. Et ainsi de suite. Le cas particulier est quand vous obtenez seulement 1 marbre à compter alors vous venez de le retourner et dire 1. laissez les autres personnes au-dessus de vous faire l'ajout que vous avez terminé.

Vous devez vous rappeler chaque fois que la fonction appelle récursivement il crée un nouveau contexte avec un sous-ensemble du problème, une fois que cette partie est résolu, il revient, de sorte que l'itération précédente pouvez compléter.

Laissez-moi vous montrer les étapes:

sumInts(a: 2, b: 5) will return: 2 + sumInts(a: 3, b: 5)
sumInts(a: 3, b: 5) will return: 3 + sumInts(a: 4, b: 5)
sumInts(a: 4, b: 5) will return: 4 + sumInts(a: 5, b: 5)
sumInts(a: 5, b: 5) will return: 5 + sumInts(a: 6, b: 5)
sumInts(a: 6, b: 5) will return: 0

Une fois que sumInts (a: 6, b: 5) a été exécuté, les résultats peuvent être calculés afin de remonter la chaîne avec les résultats que vous obtenez:

 sumInts(a: 6, b: 5) = 0
 sumInts(a: 5, b: 5) = 5 + 0 = 5
 sumInts(a: 4, b: 5) = 4 + 5 = 9
 sumInts(a: 3, b: 5) = 3 + 9 = 12
 sumInts(a: 2, b: 5) = 2 + 12 = 14.

Une Autre façon de représenter la structure de la récursivité:

 sumInts(a: 2, b: 5) = 2 + sumInts(a: 3, b: 5)
 sumInts(a: 2, b: 5) = 2 + 3 + sumInts(a: 4, b: 5)  
 sumInts(a: 2, b: 5) = 2 + 3 + 4 + sumInts(a: 5, b: 5)  
 sumInts(a: 2, b: 5) = 2 + 3 + 4 + 5 + sumInts(a: 6, b: 5)
 sumInts(a: 2, b: 5) = 2 + 3 + 4 + 5 + 0
 sumInts(a: 2, b: 5) = 14 

La récursivité est un sujet délicat à comprendre et je ne pense pas pouvoir le rendre pleinement justice ici. Au lieu de cela, je vais essayer de me concentrer sur le morceau de code particulier que vous avez ici et essayer de décrire à la fois l'intuition pour savoir pourquoi la solution fonctionne et la mécanique de la façon dont le code calcule son résultat.

Le code que vous avez donné ici résout le problème suivant: vous voulez connaître la somme de tous les entiers de a à b, inclus. Pour votre exemple, vous voulez la somme des nombres de 2 à 5, inclus, qui est

2 + 3 + 4 + 5

Lorsque vous essayez de résoudre un problème récursivement, l'une des premières étapes devrait être de comprendre comment décomposer le problème en un problème plus petit avec la même structure. Supposons donc que vous vouliez résumer les nombres de 2 à 5, inclus. Une façon de simplifier cela est de noter que la somme ci-dessus peut être réécrite comme

2 + (3 + 4 + 5)

Ici, (3 + 4 + 5) se trouve être la somme de tous les entiers compris entre 3 et 5, inclus. En d'autres termes, si vous voulez connaître la somme de tous les entiers entre 2 et 5, Commencez par calculer la somme de tous les entiers entre 3 et 5, puis ajoutez 2.

Alors, comment calculez-vous la somme de tous les entiers compris entre 3 et 5, inclus? Eh bien, cette somme est

3 + 4 + 5

Qui peut être considéré à la place comme

3 + (4 + 5)

Ici, (4 + 5) est la somme de tous les entiers entre 4 et 5 inclusivement. Donc, si vous vouliez calculer la somme de tous les nombres entre 3 et 5, inclus, vous calculeriez la somme de tous les entiers entre 4 et 5, puis ajoutez 3.

Il y a un motif ici! Si vous voulez calculer la somme des entiers entre a et b, inclus, vous pouvez faire ce qui suit. Tout d'abord, calculez la somme des entiers entre a + 1 et b, inclus. Ensuite, ajouter à ce total. Vous remarquerez que "calculer la somme des entiers entre a + 1 et b, inclusive " se trouve être à peu près le même genre de problème que nous essayons déjà de résoudre, mais avec des paramètres légèrement différents. Plutôt que de calculer de a à b, inclus, nous calculons de a + 1 à b, inclus. C'est l'étape récursive - pour résoudre le plus gros problème ("somme de a à b, inclusive"), nous réduisons le problème à une version plus petite de lui-même ("somme de a + 1 à b, inclusive.").

Si vous regardez le code ci-dessus, vous remarquerez qu'il y a cette étape en elle:

return a + sumInts(a + 1, b: b)

Ce code est simplement une traduction de la logique ci - dessus-si vous voulez additionner de a à b, inclusif, commencez par additionner a + 1 à b, inclusif (c'est l'appel récursif à sumInts), puis ajoutez a.

Bien sûr, en soi, cette approche ne fonctionnera pas réellement. Par exemple, comment calculeriez-vous la somme de tous les entiers compris entre 5 et 5 inclus? Eh bien, en utilisant notre logique actuelle, vous calculeriez la somme de tous les entiers entre 6 et 5, inclus, puis ajoutez 5. Alors, comment calculez-vous la somme de tous les entiers compris entre 6 et 5, inclus? Eh bien, en utilisant notre logique actuelle, vous calculeriez la somme de tous les entiers entre 7 et 5, inclus, puis ajoutez 6. Vous remarquerez un problème ici-cela ne cesse d'aller et aller!

Dans la résolution de problèmes récursifs,il doit y avoir un moyen d'arrêter de simplifier le problème et de le résoudre directement. Typiquement, vous trouverez un cas simple où la réponse peut être déterminée immédiatement, puis structurer votre solution pour résoudre les cas simples directement quand ils se posent. Ceci est généralement appelé un cas de base ou une base récursive .

Alors, quel est le cas de base dans ce problème particulier? Lorsque vous additionnez des entiers de a à b, inclus, si a est plus grand que b, alors la réponse est 0-Il n'y a pas de nombres dans la plage! Par conséquent, nous allons structurer notre solution comme suit:

1. Si a > b, alors la réponse est 0.
2. sinon (a ≤ b), obtenez la réponse comme suit:
   1. calculer la somme des entiers entre a + 1 et B.
   2. ajoutez un pour obtenir la réponse.

Maintenant, comparez ce pseudocode à votre code réel:

func sumInts(a: Int, b: Int) -> Int {
    if (a > b) {
        return 0
    } else {
        return a + sumInts(a + 1, b: b)
    }
}

Notez qu'il y a presque exactement une carte un-à-un entre la solution décrite dans pseudocode et ce code réel. La première étape est le cas de base - dans le cas où vous demandez la somme d'une plage vide de nombres, vous obtenez 0. Sinon, calculez la somme entre un + 1 et b, puis allez ajouter une.

Jusqu'à présent, j'ai donné juste une idée de haut niveau derrière le code. Mais vous aviez deux autres très bonnes questions. Tout d'abord, pourquoi cela ne renvoie-t-il pas toujours 0, étant donné que la fonction dit de retourner 0 si a > b ? Deuxièmement, d'où vient réellement le 14? Regardons ces facteurs à leur tour.

Essayons un cas très, très simple. Que se passe-t-il si vous appelez sumInts(6, 5)? Dans ce cas, en traçant le code, vous voyez que la fonction renvoie juste 0. C'est la bonne chose à faire, à - il n'y a pas de chiffres dans la gamme. Maintenant, essayez quelque chose de plus difficile. Que se passe-t-il lorsque vous appelez sumInts(5, 5)? Eh bien, voici ce qui se passe:

1. Vous appelez sumInts(5, 5). Nous tombons dans la branche else, qui renvoie la valeur de ' A + sumInts(6, 5).
2. pour que sumInts(5, 5) détermine ce qu'est sumInts(6, 5), nous devons mettre en pause ce que nous faisons et faire un appel à sumInts(6, 5).
3. sumInts(6, 5) est appelé. Il entre dans la branche if et renvoie 0. Cependant, cette instance de sumInts a été appelée par sumInts(5, 5), donc la valeur de retour est communiquée à sumInts(5, 5), pas à l'appelant de niveau supérieur.
4. sumInts(5, 5) peut maintenant calculer 5 + sumInts(6, 5) pour revenir 5. Il le renvoie ensuite à l'appelant de niveau supérieur.

Remarquez comment la valeur 5 a été formée ici. Nous avons commencé avec un appel actif à sumInts. Cela a déclenché un autre appel récursif, et la valeur retournée par cet appel a communiqué les informations à sumInts(5, 5). L'appel à sumInts(5, 5) a ensuite effectué un certain calcul et renvoyé une valeur à appelant.

Si vous essayez ceci avec sumInts(4, 5), Voici ce qui se passera:

• sumInts(4, 5) tente de retourner 4 + sumInts(5, 5). Pour ce faire, il appelle sumInts(5, 5).
  • sumInts(5, 5) tente de retourner 5 + sumInts(6, 5). Pour ce faire, il appelle sumInts(6, 5).
  • sumInts(6, 5) retourne 0 retour à sumInts(5, 5).</li> <li>sumInts(5, 5)now has a value forsumInts(6, 5), namely 0. It then returns5 + 0 = 5`.
• sumInts(4, 5) a maintenant une valeur de sumInts(5, 5), à savoir 5. Il retourne alors 4 + 5 = 9.

En d'autres termes, la valeur renvoyée est formée par additionner les valeurs une à la fois, en prenant chaque fois une valeur renvoyée par un appel récursif particulier à sumInts et en ajoutant la valeur actuelle de a. Lorsque la récursivité descend, l'appel le plus profond renvoie 0. Cependant, cette valeur ne quitte pas immédiatement la chaîne d'appels récursifs; au lieu de cela, elle remet simplement la valeur à l'appel récursif une couche au-dessus. De cette façon, chaque appel récursif ajoute simplement un numéro de plus et le renvoie plus haut dans la chaîne, culminant avec l'ensemble sommation. Comme un exercice, essayez de tracer ceci pour sumInts(2, 5), qui est ce que vous vouliez commencer.

J'espère que cela aide!

Vous avez de bonnes réponses ici jusqu'à présent, mais j'en ajouterai une autre qui prend une autre attitude.

Tout d'abord, j'ai écrit de nombreux articles sur des algorithmes récursifs simples que vous pourriez trouver intéressants; voir

Http://ericlippert.com/tag/recursion/

Http://blogs.msdn.com/b/ericlippert/archive/tags/recursion/

Ceux-ci sont dans l'ordre le plus récent, alors commencez par le bas.

Seconde, jusqu'à présent, toutes les réponses ont décrit la sémantique récursive en considérant l'activation de la fonction . Que chacun, chaque appel fait une nouvelle activation , et l'appel récursif s'exécute dans le contexte de cette activation. C'est une bonne façon de penser, mais il existe une méthode équivalente: smart texte de recherche et de remplacement de.

Permettez-moi de réécrire votre fonction dans une forme légèrement plus compacte; ne pensez pas à cela comme étant dans une langue particulière.

s = (a, b) => a > b ? 0 : a + s(a + 1, b)

J'espère que c'est logique. Si vous n'êtes pas familier avec l'opérateur conditionnel, il est de la forme condition ? consequence : alternative et son sens deviendra clair.

Maintenant, nous voulons évaluer s(2,5) nous le faisons en faisant un remplacement textuel de l'appel par le corps de la fonction, puis remplacez a par 2 et b par 5:

s(2, 5) 
---> 2 > 5 ? 0 : 2 + s(2 + 1, 5)

Évaluez maintenant le conditionnel. Nous remplaçons textuellement 2 > 5 par false.

---> false ? 0 : 2 + s(2 + 1, 5)

Maintenant, remplacez textuellement toutes les conditions fausses par l'alternative et toutes les conditions vraies par conséquence. Nous n'avons que de fausses conditions, donc noustextuellement remplaçons cette expression par l'alternative:

---> 2 + s(2 + 1, 5)

Maintenant, pour ne pas avoir à taper tous ces signes +, remplacez textuellement l'arithmétique constante par sa valeur. (C'est un peu une triche, mais je ne veux pas avoir à garder une trace de toutes les parenthèses!)

---> 2 + s(3, 5)

Maintenant rechercher-remplacer, cette fois avec le corps pendant l'appel, 3 pour a et 5 pour b. Nous allons mettre le remplacement de l'appel à entre parenthèses:

---> 2 + (3 > 5 ? 0 : 3 + s(3 + 1, 5))

Et maintenant, nous continuons à faire les mêmes étapes de substitution textuelle:

---> 2 + (false ? 0 : 3 + s(3 + 1, 5))  
---> 2 + (3 + s(3 + 1, 5))                
---> 2 + (3 + s(4, 5))                     
---> 2 + (3 + (4 > 5 ? 0 : 4 + s(4 + 1, 5)))
---> 2 + (3 + (false ? 0 : 4 + s(4 + 1, 5)))
---> 2 + (3 + (4 + s(4 + 1, 5)))
---> 2 + (3 + (4 + s(5, 5)))
---> 2 + (3 + (4 + (5 > 5 ? 0 : 5 + s(5 + 1, 5))))
---> 2 + (3 + (4 + (false ? 0 : 5 + s(5 + 1, 5))))
---> 2 + (3 + (4 + (5 + s(5 + 1, 5))))
---> 2 + (3 + (4 + (5 + s(6, 5))))
---> 2 + (3 + (4 + (5 + (6 > 5 ? 0 : s(6 + 1, 5)))))
---> 2 + (3 + (4 + (5 + (true ? 0 : s(6 + 1, 5)))))
---> 2 + (3 + (4 + (5 + 0)))
---> 2 + (3 + (4 + 5))
---> 2 + (3 + 9)
---> 2 + 12
---> 14

Tout ce que nous avons fait ici était juste substituion textuel simple . Vraiment, je n'aurais pas dû remplacer "3" par "2+1" et ainsi de suite jusqu'à ce que je le devais, mais pédagogiquement, cela aurait été difficile à lire.

L'activation de la fonction n'est rien de plus que de remplacer l'appel de fonction par le corps de l'appel, et de remplacer les paramètres formels par leur correspondant argument. Vous devez faire attention à introduire intelligemment les parenthèses, mais à part cela, c'est juste un remplacement de texte.

Bien sûr, la plupart des langues n'implémentent pas l'activation comme remplacement de texte, maislogiquement c'est ce que c'est.

Alors, qu'est-ce qu'une récursivité illimitée? Une récursivité où la substitution textuelle ne s'arrête pas! Remarquez comment finalement nous sommes arrivés à une étape où il n'y avait plus s à remplacer, et nous pourrait alors simplement appliquer les règles pour l'arithmétique.

La façon dont je comprends habituellement comment fonctionne une fonction récursive est en regardant le cas de base et en travaillant en arrière. Voici cette technique appliquée à cette fonction.

D'Abord le cas de base:

sumInts(6, 5) = 0

Ensuite, l'appel juste au - dessus de celui de la pile d'appels :

sumInts(5, 5) == 5 + sumInts(6, 5)
sumInts(5, 5) == 5 + 0
sumInts(5, 5) == 5

Ensuite, l'appel juste au-dessus de celui de la pile d'appels:

sumInts(4, 5) == 4 + sumInts(5, 5)
sumInts(4, 5) == 4 + 5
sumInts(4, 5) == 9

Et ainsi de suite:

sumInts(3, 5) == 3 + sumInts(4, 5)
sumInts(3, 5) == 3 + 9
sumInts(3, 5) == 12

Et ainsi de suite:

sumInts(2, 5) == 2 + sumInts(3, 5)
sumInts(4, 5) == 2 + 12
sumInts(4, 5) == 14

Notez que Nous sommes arrivés à notre appel initial à la la fonction sumInts(2, 5) == 14

L'ordre dans lequel ces appels sont exécutés:

sumInts(2, 5)
sumInts(3, 5)
sumInts(4, 5)
sumInts(5, 5)
sumInts(6, 5)

L'ordre dans lequel ces appels reviennent:

sumInts(6, 5)
sumInts(5, 5)
sumInts(4, 5)
sumInts(3, 5)
sumInts(2, 5)

Notez que nous sommes arrivés à une conclusion sur le fonctionnement de la fonction en traçant les appels dans l'ordre dans lequel ils retournent.

Je vais lui donner un aller.

En exécutant l'équation a + sumInts(a + 1, b), je vais montrer comment la réponse finale est 14.

//the sumInts function definition
func sumInts(a: Int, b: Int) -> Int {
    if (a > b) {
        return 0
    } else {
        return a + sumInts(a + 1, b)
    }
}

Given: a = 2 and b = 5

1) 2 + sumInts(2+1, 5)

2) sumInts(3, 5) = 12
   i) 3 + sumInts(3+1, 5)
   ii) 4 + sumInts(4+1, 5)
   iii) 5 + sumInts(5+1, 5)
   iv) return 0
   v) return 5 + 0
   vi) return 4 + 5
   vii) return 3 + 9

3) 2 + 12 = 14.

Laissez-nous savoir si vous avez d'autres questions.

Voici un autre exemple de fonctions récursives dans l'exemple suivant.

Un homme vient d'être diplômé de l'Université.

T est la durée en années.

Le nombre total réel d'années travaillées avant la retraite peut être calculé comme suit:

public class DoIReallyWantToKnow 
{
    public int howLongDoIHaveToWork(int currentAge)
    {
      const int DESIRED_RETIREMENT_AGE = 65;
      double collectedMoney = 0.00; //remember, you just graduated college
      double neededMoneyToRetire = 1000000.00

      t = 0;
      return work(t+1);
    }

    public int work(int time)
    {
      collectedMoney = getCollectedMoney();

      if(currentAge >= DESIRED_RETIREMENT_AGE 
          && collectedMoney == neededMoneyToRetire
      {
        return time;
      }

      return work(time + 1);
    }
}

Et cela devrait être juste assez pour déprimer tout le monde, lol. ;- P

Récursivité. En informatique, la récursivité est abordée en profondeur sous le thème des automates finis.

Dans sa forme la plus simple, c'est une référence personnelle. Par exemple, dire que "ma voiture est une voiture" est une déclaration récursive. Le problème est que la déclaration est une récursivité infinie en ce sens qu'elle ne finira jamais. La définition dans l'énoncé d'une "voiture" est que c'est une "voiture" de sorte qu'il peut être remplacé. Cependant, il n'y a pas de fin car dans le cas de substitution, il devient toujours " ma voiture est voiture".

Cela pourrait être différent si la déclaration était " ma voiture est une bentley. ma voiture est bleue."Auquel cas la substitution dans la deuxième situation pour la voiture pourrait être "bentley" résultant en "ma bentley est bleue". Ces types de substitutions sont mathématiquement expliqués en informatique par grammaires sans contexte .

La substitution réelle est une règle de production. Étant donné que L'instruction est représentée par S et que car est une variable qui peut être une "bentley" cette déclaration peut être reconstruite de manière récursive.

S -> "my"S | " "S | CS | "is"S | "blue"S | ε
C -> "bentley"

Cela peut être construit de plusieurs façons, car chaque | signifie qu'il y a un choix. S peut être remplacé par l'un de ces choix, et S commence toujours vide. Le ε signifie mettre fin à la production. Tout comme S peut être remplacé, ainsi que d'autres variables (il n'y en a qu'une et c'est C qui représenterait "bentley").

Donc, en commençant par S étant vide, et en le remplaçant par le premier choix "my"S S devient

"my"S

S peut toujours être remplacé, car il représente une variable. Nous pourrions choisir à nouveau "mon", OU ε pour y mettre fin, mais continuons à faire notre déclaration originale. Nous choisir c'est l'espace qui signifie S est remplacé par " "S

"my "S

Suivant permet de choisir C

"my "CS

Et C n'a qu'un seul choix pour le remplacement

"my bentley"S

Et l'espace à nouveau pour S

"my bentley "S

Et ainsi de suite "my bentley is"S, "my bentley is "S, "my bentley is blue"S, "my bentley is blue" (remplacer s Par ε termine le production) et nous avons récursivement construit notre déclaration "ma bentley est bleue".

Pensez à la récursivité comme ces productions et remplacements. Chaque étape du processus remplace son prédécesseur afin de produire le résultat final. Dans l'exemple exact de la somme récursive de 2 à 5, vous vous retrouvez avec la production

S -> 2 + A
A -> 3 + B
B -> 4 + C
C -> 5 + D
D -> 0

Cela devient

2 + A
2 + 3 + B
2 + 3 + 4 + C
2 + 3 + 4 + 5 + D
2 + 3 + 4 + 5 + 0
14

Je pense que la meilleure façon de comprendre les fonctions récursives est de se rendre compte qu'elles sont faites pour traiter les structures de données récursives. Mais dans votre fonction d'origine sumInts(a: Int, b: Int) qui calcule récursivement la somme des nombres de a à b, il ne semble pas être une structure de données récursive... Essayons une version légèrement modifiée sumInts(a: Int, n: Int) Où n est le nombre de chiffres que vous allez ajouter.

Maintenant, sumInts est récursif sur n, un nombre naturel. Toujours pas une donnée récursive, Non? Bon, un number pourrait être considéré comme une structure de données récursive en utilisant les axiomes Peano:

enum Natural = {
    case Zero
    case Successor(Natural)
}

Donc, 0 = Zéro, 1 = Successeur(Zéro), 2 = Successeur(Successeur(Zéro)), et ainsi de suite.

Une fois que vous avez une structure de données récursive, vous avez le modèle pour la fonction. Pour chaque cas non récursif, vous pouvez calculer la valeur directement. Pour les cas récursifs vous supposez que la fonction récursive fonctionne déjà et l'utilisez pour calculer le cas, mais déconstruire l'argument. Dans le cas des ressources Naturelles, cela signifie qu'au lieu de Succesor(n), nous allons utiliser n, ou, de manière équivalente, au lieu de n, nous allons utiliser n - 1.

// sums n numbers beginning from a
func sumInts(a: Int, n: Int) -> Int {
    if (n == 0) {
        // non recursive case
    } else {
        // recursive case. We use sumInts(..., n - 1)
    }
}

Maintenant la fonction récursive est plus simple à programmer. Tout d'abord, le cas de base, n=0. Que devrions-nous retourner si nous voulons ajouter aucun chiffre? La réponse est, bien sûr, de 0.

Et l'affaire récursive? Si nous voulons ajouter des nombres n commençant par a et que nous avons déjà une fonction sumInts qui fonctionne pour n-1? Eh bien, nous devons ajouter a et alors invoquez sumInts avec a + 1, donc nous terminons par:

// sums n numbers beginning from a
func sumInts(a: Int, n: Int) -> Int {
    if (n == 0) {
        return 0
    } else {
        return a + sumInts(a + 1, n - 1)
    }
}

La bonne chose est que maintenant vous ne devriez pas avoir besoin de penser dans le bas niveau de récursivité. Vous avez juste besoin de vérifier que:

• pour les cas de base des données récursives, il calcule la réponse sans utiliser la récursivité.
• pour les cas récursifs des données récursives, il calcule la réponse en utilisant la récursivité sur les données déstructurées.

Vous pourriez être intéressé par L'implémentation des fonctions de Nisan et Schocken. Le pdf lié fait partie d'un cours en ligne gratuit. Il décrit la deuxième partie d'une implémentation de machine virtuelle dans laquelle l'étudiant doit écrire un compilateur virtual-machine-language-to-machine-language. L'implémentation de la fonction qu'ils proposent est capable de récursivité, car elle est basée sur la pile.

Pour vous présenter l'implémentation de la fonction: considérez la machine virtuelle suivante code:

Si Swift est compilé dans ce langage de machine virtuelle, alors le bloc suivant de Code Swift:

mult(a: 2, b: 3) - 4

Compilerait jusqu'à

push constant 2  // Line 1
push constant 3  // Line 2
call mult        // Line 3
push constant 4  // Line 4
sub              // Line 5

Le langage de machine virtuelle est conçu autour d'une pile globale . push constant n pousse un entier sur cette pile.

Après l'exécution des lignes 1 et 2, la pile ressemble à:

256:  2  // Argument 0
257:  3  // Argument 1

256 et 257 sont des adresses de mémoire.

call mult pousse le numéro de ligne de retour (3) sur la pile et alloue de l'espace pour les variables locales de la fonction.

256:  2  // argument 0
257:  3  // argument 1
258:  3  // return line number
259:  0  // local 0

...et il va à l'étiquette function mult. Le code à l'intérieur de mult est exécuté. À la suite de l'exécution de ce code, nous calculons le produit de 2 et 3, qui est stocké dans la 0ème variable locale de la fonction.

256:  2  // argument 0
257:  3  // argument 1
258:  3  // return line number
259:  6  // local 0

Juste avant return ing de mult, vous remarquerez la ligne:

push local 0  // push result

Nous allons pousser le produit sur la pile.

256:  2  // argument 0
257:  3  // argument 1
258:  3  // return line number
259:  6  // local 0
260:  6  // product

Lorsque nous revenons, ce qui suit arrive:

• affiche la dernière valeur de la pile à l'adresse mémoire du 0ème argument (256 dans ce cas). Cela se trouve être l'endroit le plus pratique pour le mettre.
• jetez tout sur la pile jusqu'à l'adresse du 0ème argument.
• aller-au numéro de ligne de retour (3 dans ce cas), puis avancer.

Après le retour, nous sommes prêts à exécuter la ligne 4, et notre pile ressemble à ceci:

256:  6  // product that we just returned

Maintenant, nous poussons 4 sur le pile.

256:  6
257:  4

sub est une fonction primitive du langage de machine virtuelle. Il prend deux arguments et renvoie son résultat dans l'adresse habituelle: celle du 0ème argument.

Maintenant, nous avons

256:  2  // 6 - 4 = 2

Maintenant que vous savez comment fonctionne un appel de fonction, il est relativement simple de comprendre comment fonctionne la récursivité. Pas de magie, juste une pile.

J'ai implémenté votre fonction sumInts dans ce langage de machine virtuelle:

function sumInts 0     // `0` means it has no local variables.
  label IF
    push argument 0
    push argument 1
    lte              
    if-goto ELSE_CASE
    push constant 0
    return
  label ELSE_CASE
    push constant 2
    push argument 0
    push constant 1
    add
    push argument 1
    call sumInts       // Line 15
    add                // Line 16
    return             // Line 17
// End of function

Maintenant, je vais appeler il:

push constant 2
push constant 5
call sumInts           // Line 21

Le code s'exécute et nous arrivons jusqu'au point d'arrêt où lte renvoie false. Voici à quoi ressemble la pile à ce stade:

// First invocation
256:  2   // argument 0
257:  5   // argument 1
258:  21  // return line number
259:  2   // augend
// Second
260:  3   // argument 0
261:  5   // argument 1
262:  15  // return line number
263:  3   // augend
// Third
264:  4   // argument 0
265:  5   // argument 1
266:  15  // return line number
267:  4   // augend
// Fourth
268:  5   // argument 0
269:  5   // argument 1
270:  15  // return line number
271:  5   // augend
// Fifth
272:  6   // argument 0
273:  5   // argument 1
274:  15  // return line number
275:  0   // return value

Maintenant, nous allons "détendre" notre récursivité. return 0 et aller à la ligne 15 et avancer.

271:  5
272:  0

Ligne 16: add

271:  5

Ligne 17: return 5 et aller à la ligne 15 et avance.

267:  4
268:  5

Ligne 16: add

267:  9

Ligne 17: return 9 et aller à la ligne 15 et avance.

263:  3
264:  9

Ligne 16: add

263:  12

Ligne 17: return 12 et aller à la ligne 15 et avance.

259:  2
260:  12

Ligne 16: add

259:  14

Ligne 17: return 14 et aller à la ligne 21 et avance.

256:  14

Voilà. Récursivité: Glorifié goto.

Un très bon conseil que je suis tombé sur l'apprentissage et la compréhension de la récursivité est de passer du temps à apprendre un langage qui n'a aucune forme de construction de boucle autre que la récursivité. De cette façon, vous aurez une bonne idée de la façon d'utiliser la récursivité via la pratique.

J'ai suivi http://www.htdp.org/ qui, en plus d'être un tutoriel de schéma, est également une excellente introduction sur la façon de concevoir des programmes en termes d'architecture et de design.

Mais fondamentalement, vous besoin d'investir un peu de temps. Sans une compréhension "ferme" de la récursivité, certains algorithmes, tels que le retour en arrière, vous sembleront toujours "durs" ou même "magiques". Donc, persévérer. :- D

J'espère que cela aide et bonne chance!

Pensez à la récursivité comme un clones multiples faisant la même chose...

Vous demandez de cloner[1]: "somme des nombres entre 2 et 5"

+ clone[1]               knows that: result is 2 + "sum numbers between 3 and 5". so he asks to clone[2] to return: "sum numbers between 3 and 5"
|   + clone[2]           knows that: result is 3 + "sum numbers between 4 and 5". so he asks to clone[3] to return: "sum numbers between 4 and 5"
|   |   + clone[3]       knows that: result is 4 + "sum numbers between 5 and 5". so he asks to clone[4] to return: "sum numbers between 5 and 5"
|   |   |   + clone[4]   knows that: result is 5 + "sum numbers between 6 and 5". so he asks to clone[5] to return: "sum numbers between 6 and 5"
|   |   |   |   clone[5] knows that: he can't sum, because 6 is larger than 5. so he returns 0 as result.
|   |   |   + clone[4]   gets the result from clone[5] (=0)  and sums: 5 + 0,  returning 5
|   |   + clone[3]       gets the result from clone[4] (=5)  and sums: 4 + 5,  returning 9
|   + clone[2]           gets the result from clone[3] (=9)  and sums: 3 + 9,  returning 12
+ clone[1]               gets the result from clone[2] (=12) and sums: 2 + 12, returning 14

Et voilà!!

Il y a déjà beaucoup de bonnes réponses. Néanmoins, je suis de donner un essai.
Lorsqu'elle est appelée, une fonction obtient un espace mémoire alloué, qui est empilé sur le espace mémoire de la fonction appelant. Dans cet espace mémoire, la fonction conserve les paramètres qui lui sont transmis, les variables et leurs valeurs. Cet espace mémoire disparaît avec l'appel de retour de fin de la fonction. Comme l'idée de pile va, le espace mémoire de la fonction de l'appelant devient maintenant actif.

Pour les appels récursifs, la même fonction obtient plusieurs espace mémoire empilés les uns sur les autres. C'est tout. L'idée simple de la façon dont stack Fonctionne en mémoire d'un ordinateur devrait vous faire comprendre comment la récursivité se produit dans l'implémentation.

Un peu hors-sujet, je sais, mais... essayez de rechercher récursivité dans Google... Vous verrez par exemple ce que cela signifie :-)

Les versions antérieures de Google renvoyaient le texte suivant (Cité de mémoire):

Récursivité

Voir Récursivité

Le 10 septembre 2014, la blague sur la récursivité a été mise à jour:

Récursivité

Vouliez-vous dire: Récursivité

Pour un autre réponse, voir cette réponse.

Bon nombre des réponses ci-dessus sont très bonnes. Une technique utile pour résoudre la récursivité est cependant de préciser d'abord ce que nous voulons faire et de coder comme un humain le résoudrait . Dans le cas ci-dessus, nous voulons résumer une séquence d'entiers consécutifs (en utilisant les nombres d'en haut):

2, 3, 4, 5  //adding these numbers would sum to 14

Maintenant, notez que ces lignes sont confuses (pas mal, mais confuses).

if (a > b) {
    return 0 
}

Pourquoi le test a>b? et pourquoireturn 0

Changeons le code pour refléter de plus près ce qu'un humain fait

func sumInts(a: Int, b: Int) -> Int {
  if (a == b) {
    return b // When 'a equals b' I'm at the most Right integer, return it
  }
  else {
    return a + sumInts(a: a + 1, b: b)
  }
}

Pouvons-nous le faire encore plus humain comme? Oui! Habituellement, nous résumons de gauche à droite (2 + 3+...). Mais la récursivité ci-dessus est la somme de droite à gauche (...+4+5). Changez le code pour le refléter (le - peut être un peu intimidant, mais pas beaucoup)

func sumInts(a: Int, b: Int) -> Int {
  if (a == b) {
    return b // When I'm at the most Left integer, return it
  }
  else {
    return sumInts(a: a, b: b - 1) + b
  }
}

Certains peuvent trouver cette fonction plus déroutante puisque nous partons du "bout", mais la pratique peut la rendre naturelle (et c'est une autre bonne technique de "pensée": essayer les "deux" côtés lors de la résolution d'une récursivité). Et encore une fois, la fonction reflète ce qu'est un humain (plus?) fait: prend la somme de tous les entiers de gauche et ajoute l'entier droit 'suivant'.

J'avais du mal à comprendre la récursivité alors j'ai trouvé ce blog et j'ai déjà vu cette question alors j'ai pensé que je devais devoir partager . Vous devez lire ce blog, j'ai trouvé cela très utile d'expliquer avec pile et même expliquer comment deux récursivité fonctionne avec pile, étape par étape. Je vous recommande d'abord de comprendre comment la pile des œuvres qui explique très bien ici : voyage-de-la-pile

then now you will understand how recursion works now take a look of this post : Comprendre la récursivité étape par étape

C'est un programme:

def hello(x):
    if x==1:
        return "op"
    else:
        u=1
        e=12
        s=hello(x-1)
        e+=1
        print(s)
        print(x)
        u+=1
    return e

hello(3)

La récursivité a commencé à avoir du sens pour moi quand j'ai arrêté de lire ce que les autres disent à ce sujet ou de le voir comme quelque chose que je peux éviter et juste écrit du code. J'ai trouvé un problème avec une solution et j'ai essayé de dupliquer la solution sans regarder. J'ai seulement regardé la solution quand je suis resté impuissant. Puis je suis retourné à essayer de le dupliquer. Je l'ai fait à nouveau sur plusieurs problèmes jusqu'à ce que je développe ma propre compréhension et mon sens de la façon d'identifier un problème récursif et de le résoudre. Quand je suis arrivé à à ce niveau, j'ai commencé à inventer des problèmes et à les résoudre. Qui m'a aidé plus. Parfois, les choses ne peuvent être apprises qu'en les essayant par vous - même et en luttant; jusqu'à ce que vous "l'obteniez".