Comprendre comment fonctionnent les fonctions récursives

Question

Comme le titre l'explique, j'ai un très fondamentaux de la programmation à la question que j'ai tout simplement pas été en mesure de grok encore. Le filtrage de toutes les (très intelligent) "afin de comprendre la récursivité, vous devez d'abord comprendre la récursivité." les réponses issues de différents threads, je ne suis toujours pas tout à fait obtenir.

Comprendre que, face à ne sachant pas ce que nous ne savons pas, nous avons tendance à poser les mauvaises questions ou poser les bonnes questions à tort, je vais partager ce que je "pense" ma question est dans l'espoir que quelqu'un avec une perspective analogue peut partager un peu de connaissances qui aideront à leur tour sur le récursive ampoule pour moi!

Ici est la fonction (la syntaxe est écrit dans Swift):

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

Nous allons utiliser 2 et 5 comme arguments:

println(sumInts(a: 2, b: 5))

Évidemment la réponse est 14. Mais je ne suis pas clair sur la façon dont cette valeur est atteinte.

Ce sont mes 2 décrochements:

1. La fonction est appelée récursivement jusqu'à ce qu'une condition est remplie. Cette condition est un > b. Lorsque cette condition est remplie, retour à 0. Au premier coup d'œil, j'attendrais le retour de la valeur à 0, ce qui est manifestement inexact.

2. L'impression de la valeur de 'a' à chaque itération donne une valeur qui je l'espère: 2, 3, 4, 5 (à quel point 5+1 > b qui satisfait à la première condition: a > b) mais je ne vois pas comment la valeur de 14 ans est atteint.

Ma première pensée est que quelque chose de semblable à la suivante se passe comme par magie:

var answer = a;
answer += a+1 until a > b;
return answer;   

Donc écarté de la magie, je suis tout simplement pas obtenir quelque chose. J'aimerais comprendre ce qui se passe plus que juste implicitement.

Si quelqu'un pouvait m'expliquer ce que techniquement il arrive lors de ce type de fonction et pourquoi le résultat n'est pas 0, et comment, finalement, a + sumInts(a: a + 1, b: b) = 14, je serais toujours à votre dette.

Answer 1

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, retour à 0. Au premier coup d'œil, j'attendrais le retour de la valeur à 0, ce qui est manifestement inexact.

Voici ce que l'ordinateur de calcul sumInts(2,5) pense que si elle é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, certains appellent à la fonction sumInts renvoie en fait 0 cependant ce n'est pas la valeur finale parce que l'ordinateur a toujours ajouter 5 à 0, puis 4 à la suite, puis 3, puis 2, tel que décrit par les quatre dernières phrases de la pensée de notre ordinateur. Notez que dans la récursivité, l'ordinateur n'a pas seulement pour calculer l'appel récursif, il faut aussi garder en mémoire que faire avec la valeur retournée par l'appel récursif. Il y a une zone spéciale de la mémoire de l'ordinateur appelé la pile où ce type d'information est enregistrée, cet espace est limité et les fonctions qui sont trop récursive peut épuiser la pile: c'est le débordement de la pile de donner son nom à notre plus aimé site web.

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

2.L'impression de la valeur de 'a' à chaque itération donne une valeur qui je l'espère: 2, 3, 4, 5 (à quel point 5+1 > b qui satisfait à la première condition: a > b) mais je ne vois pas comment la valeur de 14 ans est atteint.

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.

Answer 2

Je pense que la confusion est issu de la pensée comme de "la même fonction" d'être appelé à de nombreuses reprises. Si vous pensez à elle comme "autant de copies de la même fonction appelée", alors il peut être plus clair:

Une seule copie de la fonction jamais renvoie la valeur 0, et ce n'est pas la première (c'est la dernière). De sorte que le résultat de l'appel de la première n'est pas 0.

Pour le deuxième bit de confusion, je pense qu'il sera plus facile de préciser la récursivité en anglais. Lire cette ligne:

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

"de retour la valeur de 'a' plus (la valeur de retour d'une autre copie de la fonction, qui est la copie de la valeur de 'a' plus (la valeur de retour d'une autre copie de la fonction, qui est la deuxième copie de la valeur de 'a' plus (...", avec chaque copie de la fonction de frai une nouvelle copie de lui-même avec une augmentation de 1, jusqu'à ce que a > b condition est remplie.

Au moment où vous atteignez la la une > b condition d'être vrai, vous avez un (potentiellement arbitrairement) le long de la pile de copies de la fonction à tous dans le milieu de l'exécution, tous les en attente sur le résultat de la copie suivante pour savoir ce qu'ils doivent ajouter à 'a'.

(edit: aussi, quelque chose à être conscient, c'est que la pile de copies de la fonction que j'ai mentionner, c'est une chose réelle qui prend de la mémoire réelle, et le plantage de votre programme si elle devient trop grande. Le compilateur peut optimiser dans certains cas, mais épuisante espace de pile est grave et malheureux limitation des fonctions récursives en de nombreuses langues)

Answer 3

Pour comprendre la récursivité, vous devez considérer le problème de manière différente. Au lieu d'une grande logique de la séquence d'étapes qui fait sens comme un tout, au contraire, vous prenez un gros problème et de le diviser en plus petits problèmes et de résoudre les ceux qui, une fois que vous avez une réponse pour les sous-problèmes que vous combiner les résultats de la sous-problèmes pour faire la solution du problème plus important. Pensez à vous et à vos amis, avoir besoin de compter le nombre de billes dans un grand seau. Vous n'chaque prendre un petit seau et d'aller compter ceux individuellement et lorsque vous avez terminé d'ajouter le totaux ensemble.. et Bien maintenant si chacun de vous trouver des amis et de diviser les seaux de plus, alors vous avez juste besoin d'attendre pour ces autres amis à la figure de leurs totaux, le ramener à chacun de vous, vous l'ajoutez. Et ainsi de suite. Le cas particulier est quand vous obtenez seulement 1 marbre de compter ensuite, vous avez juste retourner en arrière et dire 1. laisser l'autre des personnes ci-dessus, vous ne l'ajout que vous avez terminé.

Vous devez vous rappeler à chaque fois que la fonction s'appelle elle-même de manière récursive, 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.

Permettez-moi de 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 sumInts(a: 6, b: 5) a exécuté, le résultat peut être calculé de manière à 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 

Answer 4

La récursivité est un sujet difficile à comprendre et je ne pense pas que je peux parfaitement faire la justice ici. Au lieu de cela, je vais essayer de mettre l'accent sur le morceau de code que vous avez ici et essayer de décrire à la fois l'intuition pour expliquer pourquoi la solution des œuvres et de 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 savoir la somme de tous les entiers de a à b, inclusivement. Pour votre exemple, vous souhaitez que la somme des nombres de 2 à 5 inclus, ce qui est

2 + 3 + 4 + 5

Lorsque vous essayez de résoudre un problème de manière récursive, l'une des premières étapes devraient être de comprendre comment diviser le problème en un petit problème avec la même structure. Donc, supposons que vous voulais résumer les nombres de 2 à 5 inclusivement. Une façon de simplifier ce qui est à remarquer 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 nombres entiers compris entre 3 et 5 inclusivement. En d'autres termes, si vous voulez savoir la somme de tous les nombres entiers compris entre 2 et 5, commencez par calculer la somme de tous les nombres entiers compris entre 3 et 5, puis ajouter 2.

Alors comment faire pour calculer la somme de tous les nombres entiers compris entre 3 et 5, inclusive? Eh bien, cette somme est

3 + 4 + 5

qui peuvent être considérés plutôt comme des

3 + (4 + 5)

Ici, (4 + 5) est la somme de tous les nombres entiers compris entre 4 et 5 inclusivement. Donc, si vous voulez calculer la somme de tous les nombres compris entre 3 et 5, inclusive, vous souhaitez calculer la somme de tous les nombres entiers compris entre 4 et 5, puis ajouter 3.

Il y a un modèle ici! Si vous voulez calculer la somme des entiers compris entre a et b, inclusive, vous pouvez effectuer les opérations suivantes. Tout d'abord, calculer la somme des entiers compris entre un + 1 et b inclus. Ensuite, ajouter à ce total. Vous remarquerez que "calculer la somme des entiers compris entre un + 1 et b, inclusive" qui arrive à être à peu près le même genre de problème que nous sommes déjà en train de résoudre, mais avec un peu de paramètres différents. Plutôt que de l'informatique de a à b, inclusive, nous sommes le calcul de un + 1 pour b, inclusivement. C'est le récursive étape pour résoudre le problème le plus important ("la somme de a à b, inclusive"), on réduit le problème à une plus petite version de lui-même ("la somme de a + 1 b, inclusivement.").

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

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

Ce code est simplement une traduction de la logique ci-dessus - si vous souhaitez calculer la somme de a à b, inclusive, à commencer par la somme de un + 1 pour b, inclusive (c'est l'appel récursif à l' sumInts), puis ajouter a.

Bien sûr, en soi, cette approche ne fait pas travailler. Par exemple, comment voulez-vous calculer la somme de tous les nombres entiers compris entre 5 et 5 inclusivement? Eh bien, à l'aide de notre logique actuelle, vous souhaitez calculer la somme de tous les nombres entiers compris entre 6 et 5, inclusive, puis ajoutez 5. Alors comment faire pour calculer la somme de tous les nombres entiers compris entre 6 et 5, inclusive? Eh bien, à l'aide de notre logique actuelle, vous souhaitez calculer la somme de tous les nombres entiers compris entre 7 et 5 inclusivement, puis ajouter 6. Vous remarquerez un problème ici - ce qui ne cesse d'avancer et d'aller!

Dans récursifs résolution de problème, il doit y avoir un moyen d'arrêter de simplifier le problème et, au lieu de simplement aller de le résoudre directement. Généralement, vous trouverez un cas simple où la réponse peut être déterminée immédiatement, puis la structure de votre solution pour résoudre les cas les plus simples directement lorsqu'ils surviennent. Ce qui est généralement appelé un cas de base ou une récursif de base.

Quel est donc le cas de base dans ce problème particulier? Lorsque vous êtes en additionnant les nombres entiers de a à b, inclusive, si l'un se trouve être plus grand que b, alors la réponse est 0 - il n'y a pas tous les numéros de la plage! Donc, nous allons structurer notre solution comme suit:

1. Si a > b, alors la réponse est 0.
2. Sinon, (a ≤ b), obtenir la réponse suivante:
   1. Calculer la somme des entiers compris entre un + 1 et b.
   2. Ajouter un pour obtenir la réponse.

Maintenant, comparez cette pseudo-code de votre code:

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

Notez qu'il n'y a presque exactement un one-to-one de la carte entre la solution décrite dans le pseudo-code et ce code. La première étape est le cas de base - dans le cas où vous vous demandez pour la somme de vide plage de numéros, vous obtenez 0. Sinon, calculer la somme entre un + 1 et b, puis allez ajouter une.

Jusqu'à présent, j'ai donné juste un de haut niveau de l'idée derrière le code. Mais vous avez eu deux autres, très bonnes questions. Tout d'abord, pourquoi n'est-il pas toujours de retour 0, étant donné que la fonction dit de renvoyer 0 si a > b? En deuxième lieu, le 14 proviennent en réalité d'? Regardons ces facteurs à leur tour.

Essayons un très, cas très simple. Qu'advient-il si vous appelez sumInts(6, 5)? Dans ce cas, la traçabilité par le code, vous verrez que la fonction retourne 0. C'est la bonne chose à faire, il ne sont pas tous les numéros de la plage. Maintenant, essayez quelque chose de plus difficile. Ce qui se passe lorsque vous appelez sumInts(5, 5)? Eh bien, voici ce qui arrive:

1. Vous appelez sumInts(5, 5). Nous tombons dans l' else de la branche, qui renvoie la valeur de " a + sumInts(6, 5).
2. Pour sumInts(5, 5) afin de déterminer ce qu' sumInts(6, 5) est, nous avons besoin de faire une pause, ce que nous faisons et faire un appel à l' sumInts(6, 5).
3. sumInts(6, 5) est appelée. Il pénètre dans l' if de la branche et les retours 0. Toutefois, cette instance de sumInts a été appelé par sumInts(5, 5), de sorte que la valeur de retour est communiquée sumInts(5, 5), pas de haut-niveau de l'appelant.
4. sumInts(5, 5) peut maintenant calculer 5 + sumInts(6, 5) de revenir 5. Il retourne ensuite au niveau supérieur de l'appelant.

Remarquez que la valeur 5 a été formé ici. Nous avons commencé avec un appel en sumInts. Qui a lancé un autre appel récursif, et la valeur retournée par l'appel communiqué les informations à la sumInts(5, 5). L'appel à l' sumInts(5, 5) ensuite tour à tour fait un peu de calcul et a retourné une valeur de retour à l'appelant.

Si vous essayez cela avec sumInts(4, 5), voici ce qui va arriver:

• sumInts(4, 5) essaie de revenir 4 + sumInts(5, 5). Pour ce faire, il appelle sumInts(5, 5).
  • sumInts(5, 5) essaie de revenir 5 + sumInts(6, 5). Pour ce faire, il appelle sumInts(6, 5).
  • sumInts(6, 5) retourne 0 retour à l' 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 retournée est formé en additionnant les valeurs une par une, en prenant à chaque fois une valeur renvoyée par un appel récursif à l' sumInts , et en ajoutant la valeur courante de a. Lorsque la récursivité de fond, la plus profonde de l'appel renvoie 0. Cependant, cette valeur n'est pas immédiatement à la sortie de l'appel récursif de la chaîne; au lieu de cela, c'est juste les mains de la valeur de retour de l'appel récursif une couche au-dessus d'elle. De cette façon, chaque appel récursif ajoute simplement dans un plus grand nombre et renvoie plus haut dans la chaîne, culminant avec l'ensemble de la sommation. Comme exercice, essayez de suivre ce pour sumInts(2, 5), ce qui est ce que vous vouliez commencer avec.

Espérons que cette aide!

Answer 5

Vous avez de bonnes réponses jusqu'ici, mais je vais en ajouter un de plus qui prend une approche différente.

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

http://ericlippert.com/tag/recursion/

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

Ceux-ci sont à nouveau au-dessus de l'ordre, donc, commencer par le bas.

Deuxièmement, jusqu'à présent, toutes les réponses ont décrit la sémantique récursive en considérant la fonction d'activation. Que chaque, à chaque appel 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 text recherche et remplacement.

Permettez-moi de réécrire votre fonction en un peu plus de forme compact; ne pensez pas à ce que d'être dans une langue donnée.

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

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

Maintenant, nous souhaitons évaluer l' s(2,5) Nous le faisons en faire un texte à la place de l'appel avec le corps de la fonction, puis replacez - a avec 2 et b avec 5:

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

Maintenant évaluer la condition. Nous textuellement remplacer 2 > 5 avec false.

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

Maintenant textuellement remplacer toutes les fausses conditionnelles à l'autre et toutes les véritables conditions avec la conséquence. Nous avons seulement faux conditionnelles, nous avons donc textuellement remplacer cette expression à l'autre:

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

Maintenant, pour m'épargner d'avoir à les saisir de tous ceux - + signes, textuellement remplacer constante de l'arithmétique avec sa valeur. (C'est un peu de la triche, mais je ne veux pas avoir à garder une trace de tous 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 devons juste continuer à faire ces mêmes textuelle de substitution suit:

---> 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

Tous nous avons fait ici est juste simple substitution textuelle. Vraiment, je ne devrais pas avoir substitué "3" "2+1" et ainsi de suite jusqu'à ce que je devais, mais sur le plan pédagogique, il serait devenu difficile à lire.

Activation de la fonction est rien de plus que de remplacer l'appel de la fonction avec le corps de l'appel, et en remplaçant les paramètres formels avec des arguments correspondants. Vous devez être prudent sur l'introduction des parenthèses de façon intelligente, mais à part ça, c'est juste de remplacement de texte.

Bien sûr, la plupart des langues ne sont pas réellement de mettre en œuvre l'activation comme texte de remplacement, mais logiquement c'est ce qu'il est.

Alors que est une surabondance de la récursivité? Une récursivité où le texte de substitution ne s'arrête pas! Remarquez comment, finalement, nous sommes arrivés à une étape où il n'y avait pas plus d' s pour le remplacer, et nous pourrions alors il suffit d'appliquer les règles de l'arithmétique.