Supposons que j'ai une boucle pour Foo.Recursion Tracing
int Foo(int n)
{
if (n <= 1)
return 2;
else
return Foo(n-1) * Foo(n-2) * Foo (n-3);
}
Combien d'appel aura lieu si j'appelle Foo (3) et quel serait le résultat ...
Merci
Foo(3) appels Foo(2), Foo(1) et Foo(0)
Foo(1) et Foo(0) retourner immédiatement. Appliquez maintenant la même logique pour Foo(2), qui ne revient pas immédiatement.
Pour obtenir le résultat, dessiner un arbre comme celui-ci:
Foo(3)
/ | \
Foo(2) Foo(1) Foo(0)
Continuer dessiner l'arbre jusqu'à ce que vous avez des appels récursifs qui retournent immédiatement (pour lesquels les premiers if renvoie true), puis utilisez les résultats pour calculer les valeurs qui sont plus élevées dans l'arbre.
Vous pouvez utiliser l'arborescence pour déterminer le nombre d'appels récursifs effectués.
@bubdada: Alors, pour être sûr de bien comprendre, essayez-le avec Foo (5). Prenez note du nombre de fois où vous finissez par appeler la fonction pour une valeur d'entrée donnée (par exemple, combien de fois finissez-vous par appeler Foo (0), Foo (1), Foo (2), Foo (3), Foo (4), et Foo (5)?). Pour plus de crédit, trouver un moyen de réduire la duplication, étant donné que Foo devrait retourner la même valeur étant donné la même entrée. –
Col 1: Foo (3)
Col 2: Foo (2) * Foo (1) * Foo (0)
Col 3: Foo (1) * Foo (0) * Foo (-1) * 2 * 2
Résultat: 2 * 2 * 2 * 2 * 2 = 32
Foo (3) se serait appelé 7 fois.
Que diriez-vous:
int Foo(int n)
{
cout << "Foo(" << n << ")" << endl;
if (n <= 1)
return 2;
else
return Foo(n-1) * Foo(n-2) * Foo (n-3);
}
Pourquoi courez-vous pas et savoir? –
Je dois être en mesure d'échanger à la main je m'attends à quelque chose de similaire à cela dans l'examen: D – bubdada
7 appels: http://ideone.com/0LU9T – zengr