Comprendre la récursion ici

Question

Je regarde un problème récursif où un enfant peut sauter un escalier d'étapes n en 1,2 ou 3 étapes en même temps. Le code que je regarde est une fonction similaire à celle de fibonacci. Cependant, ce que je ne comprends pas, c'est si n == 0 pourquoi retourne-t-il 1. Si le nombre total de pas est 0, ne devrait-il pas y avoir zéro moyen de l'escalader? Pourquoi y a-t-il un moyen de l'escalader?

int f(int n) 
{ 
if(n<0) 
return 0; 
else if(n==0) 
return 1; 
else 
return f(n-1) + f(n-2) + f(n-3); 
} 

Answer 1

Il s'agit davantage d'une question de logique. Supposons que vous restiez là et ne fassiez rien. Combien de pas avez-vous grimpé? La réponse est zéro. Alors, avez-vous réussi à grimper à pas zéro? Oui.

Combien de façons y a-t-il d'escalader les escaliers zéro? Juste une façon: vous devez rester là et ne pas monter les marches.

Answer 2

Ce n'est pas vraiment une question valide. Comme il s'agit d'une implémentation récursive, vous devez toujours fournir un cas limite pour f(nmin) où nmin est 1 inférieur au n valide le plus bas.

Le cas n = 0 est donc une condition aux limites qui sert à garantir le résultat correct pour toutes les valeurs où n > 0. En d'autres termes, cela (probablement) ne signifie rien, ou, cela signifie probablement quelque chose de différent de ce que vous pensez que cela signifie. Tout ce qu'il a à faire est d'assurer un résultat correct pour f(1).

Non, il n'y a pas 0 moyens pour monter les escaliers 0, de la même manière que 0/0 ne est pas égal 0. C'est un résultat indéterminé.