Récursivité

Bonjour, j’ai besoin de votre aide pour cette exercice en photo, j’ai plus ou moins compris l’algorithme et j’ai répondu à la question 1 et 2 mais je n’arrive pas à expliquer celles d’après, quelqu’un pourrait m’aider svp?

Lol, pas l'habitude du python. 
Mais bon, j'avais déduit ce que faisaient [:1] et [-1].

Par contre, j'avoue que j'ai mis du temps à comprendre ce que faisait cette fonction (le nom "rendu" m'a un peu perdu, je pensais qu'on s'occupait du montant à rendre ).
Bon, en fait la question 4) donnait la réponse.

Alors, pour t'aider, il faut déjà bien comprendre ce que fait l'algo.
Il cherche à déterminer le nombre de possibilités pour atteindre une somme avec des pièces de montants différents (peu importe le nombre de chacune).

Donc l'algo part du principe, pour un montant et des valeurs de pièces différentes (triées dans l'ordre) :
- d'enlever une valeur de pièce (sans l'utiliser, donc montant inchangé) et de voir le nombre de combinaisons possible pour le montant de départ en n'utilisant que les autres valeurs de pièces inférieures.
- d'utiliser la valeur une fois (on l'a déduit du montant), et de voir le nombre de combinaisons pour ce nouveau montant avec les mêmes valeurs de pièces

Les conditions d'arrêt :
- le montant est devenu négatif : on retourne 0, la combinaison est impossible (on a utilisé une pièce trop grande pour le montant).
- le montant est positif ou nul (je vais y revenir), mais on n'a plus de valeurs de pièces : on retourne 0, cette combinaison n'est pas possible
- Récursivité : le montant est positif et on a encore des valeurs de pièces, on continue la récursivité, on a pas finit le boulot.
- le montant est égal à 0, et il nous reste des valeurs de pièces. On considère donc que  l'on a trouvé une possibilité, on retourne 1.

J'avoue, que l'aspect un peu perturbant, c'est le cas où len(piece) == 0.
A ce moment là, on est dans le cas où montant >= 0.
Si montant est positif, ce n'est pas un problème, on continue la récursivité.

Mais donc si montant=0 et plus de pièces, cela veut dire quoi ?
On pourrait se dire que de ne pas avoir de pièces, mais pour rien rembourser, c'est que l'on est arrivé au bout d'une possibilité.

Mais normalement, lorsque montant tombe à 0 (et donc que l'on a une possibilité), c'est lorsque l'on effectue nb_rendus(montant -pieces[-1], pieces).  Donc, que l'on a forcément encore des pièces.
Et cette possibilité retourne effectivement 1 donc notre cas d'arrêt.
(bref, logiquement, on ne tombe jamais dans le cas montant=0 et pieces=[]).

Pour les questions 4) et 5), il suffit de faire tourner le code.
(par exemple ici : https://www.programiz.com/python-programming/online-compiler/)

4) On trouve la réponse pour nb_rendus(81, [1,5,10,25,50]).

5) On a effectivement une erreur. on atteint une récursivité au delà des limites (le compilateur coupe, pensant avoir à faire à une récursivité infinie).

Ils font référence à la fonction fibo (pour la suite de Fibonacci je suppose ?). Donc à une astuce en particulier, vu éventuellement précédemment dans la suite d'exercice.
Mais là, comme ça, je ne vois pas ... du moins en gardant la même idée d'algorithme.

Sinon, je ne sais pas, je partirais sans doute avec des modulos et divisions entières (genre combien de fois vont 50 dans mon montant ? je multiplie ça par le nombre de possibilités pour obtenir 50 et j'ajoute le nombre de possibilité pour le modulo) ... mais en faisant gaffe de ne pas compter deux fois des combinaison similaires. Pas forcément la bonne approche du coup ...