Langage C

Une donnée récursive est exploitée aisément avec un algorithme récursif, mais ce n'est pas une condition nécessaire pour écrire un code récursif.

Oui, un code récursif correct doit utiliser un test d'arrêt pour sortir de la boucle d'appels, et éviter un bouclage infini qui se traduit, sur une machine, par un arrêt suite à un débordement de mémoire.

Cette clause sinon, plus ou moins complexe, contiendra l'appel récursif.

Notez que, selon la formulation du test, les rôles des clauses alors et sinon peuvent être inversés.

Une décomposition d'un problème sur un domaine de données en sous-problèmes sur des sous-domaines réduits afin d'approcher les cas triviaux dont les résultats sont connus du principe de récursivité. C'est une application du paradigme « diviser pour régner ».

Les fonctions récursives nécessitent une valeur de retour, mais une procédure peut être récursive avec comme résultat un effet de bord.

C'est le principe de la récursivité, soit une application du même code sur un ensemble partiel de données initiales.

Partiellement vrai. L'exécution de f1 provoquant l'exécution de f2 qui passe par une fonction f3, elle-même, appelant f1 est possible.

Ce cas intègre les cas de récursivité croisée simples (2 fonctions) ou multiples (plus de 2 fonctions intervenantes).

La récursivité croisée peut être contrôlée dans une seule fonction.

L'appel n'est pas la dernière chose exécutée. La somme est réalisée à la suite.

L'appel n'est pas la dernière chose exécutée. La multiplication est réalisée à la suite.

Un appel récursif est un appel à la même fonction ou procédure.

Pas nécessairement. Il peut n'y avoir qu'un cas d'arrêt et une décomposition du problème en plusieurs sous-problèmes.

Une récursivité multiple pour une fonction est une propriété liée uniquement à la fonction.

Cela peut être le cas, mais il n'est pas nécessaire. Nous verrons par la suite un exemple.

Pas nécessairement. Cela dépend de la nature du problème à résoudre.

Il n'est pas nécessaire d'avoir tous les paramètres intervenant dans le test d'arrêt.

Le mécanisme de gestion des appels par une machine à pile permet ce type d'instruction.

L'appel ne se termine pas, mais c'est l'appel « morris(m, n) ». Ainsi, l'évaluation du paramètre provoque une descente infinie. En fait, l'exécution de « morris(m - 1, morris(m, n)) » ne commencera jamais !

Oui ! En effet, cet appel récursif utilise les mêmes paramètres. Nous obtenons une suite d'appels pour laquelle le test d'arrêt ne sera jamais vrai (sauf s'il est satisfait par les valeurs transmises par l'appel initial).