Comprendre la récursivité [fermé]

J'ai de la difficulté à comprendre la récursivité à l'école. Chaque fois que le professeur en parle, il me semble que je comprends, mais dès que je l'essaye par moi-même, cela me fait complètement sauter la cervelle.

J'essayais de résoudre Towers of Hanoi toute la nuit et j'ai complètement sidéré. Mon manuel n'a que 30 pages en récursivité donc ce n'est pas trop utile. Quelqu'un connaît-il des livres ou des ressources qui peuvent aider à clarifier ce sujet?

Comment vider un vase contenant cinq fleurs?

Réponse: si le vase n'est pas vide, vous enlevez une fleur puis vous videz un vase contenant quatre fleurs.

Comment vider un vase contenant quatre fleurs?

Réponse: si le vase n'est pas vide, vous enlevez une fleur puis vous videz un vase contenant trois fleurs.

Comment vider un vase contenant trois fleurs?

Réponse: si le vase n'est pas vide, vous enlevez une fleur puis vous videz un vase contenant deux fleurs.

Comment vider un vase contenant deux fleurs?

Réponse: si le vase n'est pas vide, vous enlevez une fleur puis vous videz un vase contenant une fleur.

Comment vider un vase contenant une fleur?

Réponse: si le vase n'est pas vide, vous enlevez une fleur puis vous videz un vase ne contenant aucune fleur.

Comment vider un vase sans fleurs?

Réponse: si le vase n'est pas vide, vous enlevez une fleur mais le vase est vide donc vous avez terminé.

C'est répétitif. Généralisons-le:

Comment vider un vase contenant N fleurs?

Réponse: si le vase n'est pas vide, vous enlevez une fleur puis vous videz un vase contenant N-1 fleurs.

Hmm, pouvons-nous voir cela dans le code?

void emptyVase( int flowersInVase ) {
  if( flowersInVase > 0 ) {
   // take one flower and
    emptyVase( flowersInVase - 1 ) ;

  } else {
   // the vase is empty, nothing to do
  }
}

Hmm, ne pourrions-nous pas simplement faire ça dans une boucle for?

Pourquoi, oui, la récursivité peut être remplacée par l'itération, mais souvent la récursivité est plus élégante.

Parlons des arbres. En informatique, un arbre est une structure composée de nœuds , où chaque nœud a un certain nombre d'enfants qui sont également des nœuds, ou nuls. Un arbre binaire est un arbre composé de nœuds qui ont exactement deux enfants, généralement appelés "gauche" et "droite"; encore une fois, les enfants peuvent être des nœuds ou nuls. Une racine est un nœud qui n'est l'enfant d'aucun autre nœud.

Imaginez qu'un nœud, en plus de ses enfants, ait une valeur, un nombre, et imaginez que nous souhaitons additionner toutes les valeurs dans un arbre.

Pour additionner la valeur dans n'importe quel nœud, nous ajouterions la valeur du nœud lui-même à la valeur de son enfant gauche, le cas échéant, et la valeur de son enfant droit, le cas échéant. Rappelons maintenant que les enfants, s'ils ne sont pas nuls, sont également des nœuds.

Donc, pour additionner l'enfant gauche, nous ajouterions la valeur du nœud enfant lui-même à la valeur de son enfant gauche, le cas échéant, et la valeur de son enfant droit, le cas échéant.

Donc, pour additionner la valeur de l'enfant gauche de l'enfant gauche, nous ajouterions la valeur du nœud enfant lui-même à la valeur de son enfant gauche, le cas échéant, et la valeur de son enfant droit, le cas échéant.

Peut-être que vous avez anticipé où je vais avec cela et que vous aimeriez voir du code? D'ACCORD:

struct node {
  node* left;
  node* right;
  int value;
} ;

int sumNode( node* root ) {
  // if there is no tree, its sum is zero
  if( root == null ) {
    return 0 ;

  } else { // there is a tree
    return root->value + sumNode( root->left ) + sumNode( root->right ) ;
  }
}

Notez qu'au lieu de tester explicitement les enfants pour voir s'ils sont nuls ou des nœuds, nous faisons simplement que la fonction récursive retourne zéro pour un nœud nul.

Supposons donc que nous ayons un arbre qui ressemble à ceci (les nombres sont des valeurs, les barres obliques pointent vers les enfants et @ signifie que le pointeur pointe vers null):

     5
    / \
   4   3
  /\   /\
 2  1 @  @
/\  /\
@@  @@

Si nous appelons sumNode à la racine (le nœud avec la valeur 5), nous retournerons:

return root->value + sumNode( root->left ) + sumNode( root->right ) ;
return 5 + sumNode( node-with-value-4 ) + sumNode( node-with-value-3 ) ;

Développons cela en place. Partout où nous verrons sumNode, nous le remplacerons par l'extension de l'instruction return:

sumNode( node-with-value-5);
return root->value + sumNode( root->left ) + sumNode( root->right ) ;
return 5 + sumNode( node-with-value-4 ) + sumNode( node-with-value-3 ) ;

return 5 + 4 + sumNode( node-with-value-2 ) + sumNode( node-with-value-1 ) 
 + sumNode( node-with-value-3 ) ;  

return 5 + 4 
 + 2 + sumNode(null ) + sumNode( null )
 + sumNode( node-with-value-1 ) 
 + sumNode( node-with-value-3 ) ;  

return 5 + 4 
 + 2 + 0 + 0
 + sumNode( node-with-value-1 ) 
 + sumNode( node-with-value-3 ) ; 

return 5 + 4 
 + 2 + 0 + 0
 + 1 + sumNode(null ) + sumNode( null )
 + sumNode( node-with-value-3 ) ; 

return 5 + 4 
 + 2 + 0 + 0
 + 1 + 0 + 0
 + sumNode( node-with-value-3 ) ; 

return 5 + 4 
 + 2 + 0 + 0
 + 1 + 0 + 0
 + 3 + sumNode(null ) + sumNode( null ) ; 

return 5 + 4 
 + 2 + 0 + 0
 + 1 + 0 + 0
 + 3 + 0 + 0 ;

return 5 + 4 
 + 2 + 0 + 0
 + 1 + 0 + 0
 + 3 ;

return 5 + 4 
 + 2 + 0 + 0
 + 1 
 + 3  ;

return 5 + 4 
 + 2 
 + 1 
 + 3  ;

return 5 + 4 
 + 3
 + 3  ;

return 5 + 7
 + 3  ;

return 5 + 10 ;

return 15 ;

Voyons maintenant comment nous avons conquis une structure de profondeur arbitraire et de "branchie", en la considérant comme l'application répétée d'un modèle composite? à chaque fois par le biais de notre fonction sumNode, nous avons traité un seul nœud, en utilisant une seule branche if / then, et deux instructions de retour simples qui ont presque écrit elles-mêmes, directement à partir de notre spécification?

How to sum a node:
 If a node is null 
   its sum is zero
 otherwise 
   its sum is its value 
   plus the sum of its left child node
   plus the sum of its right child node

Voilà le pouvoir de la récursivité.

L'exemple de vase ci-dessus est un exemple de récursivité de la queue . Tout ce que signifie la récursion de queue , c'est que dans la fonction récursive, si nous récursions (c'est-à-dire, si nous appelions à nouveau la fonction), c'était la dernière chose que nous faisions.

L'exemple d'arbre n'était pas récursif à la queue, car même si cette dernière chose que nous avons faite était de soigner l'enfant droit, avant de le faire, nous avons récursé l'enfant gauche.

En fait, l'ordre dans lequel nous avons appelé les enfants et ajouté la valeur du nœud actuel n'a pas d'importance du tout, car l'addition est commutative.

Voyons maintenant une opération où l'ordre est important. Nous utiliserons un arbre binaire de nœuds, mais cette fois la valeur retenue sera un caractère, pas un nombre.

Notre arbre aura une propriété spéciale, pour tout nœud, son caractère vient après (par ordre alphabétique) le caractère détenu par son enfant gauche et avant (par ordre alphabétique) le caractère détenu par son enfant droit.

Ce que nous voulons faire, c'est imprimer l'arbre dans l'ordre alphabétique. C'est facile à faire, étant donné la propriété spéciale de l'arbre. Nous imprimons simplement l'enfant gauche, puis le caractère du nœud, puis l'enfant droit.

Nous ne voulons pas simplement imprimer bon gré mal gré, nous allons donc passer notre fonction quelque chose à imprimer. Ce sera un objet avec une fonction print (char); nous n'avons pas à nous soucier de son fonctionnement, juste que lorsque print est appelé, il imprime quelque chose, quelque part.

Voyons cela dans le code:

struct node {
  node* left;
  node* right;
  char value;
} ;

// don't worry about this code
class Printer {
  private ostream& out;
  Printer( ostream& o ) :out(o) {}
  void print( char c ) { out << c; }
}

// worry about this code
int printNode( node* root, Printer& printer ) {
  // if there is no tree, do nothing
  if( root == null ) {
    return ;

  } else { // there is a tree
    printNode( root->left, printer );
    printer.print( value );
    printNode( root->right, printer );
}

Printer printer( std::cout ) ;
node* root = makeTree() ; // this function returns a tree, somehow
printNode( root, printer );

En plus de l'ordre des opérations qui importe maintenant, cet exemple illustre que nous pouvons passer des choses dans une fonction récursive. La seule chose que nous devons faire est de nous assurer qu'à chaque appel récursif, nous continuons à le transmettre. Nous avons passé un pointeur de noeud et une imprimante à la fonction, et à chaque appel récursif, nous les avons passés "vers le bas".

Maintenant, si notre arbre ressemble à ceci:

         k
        / \
       h   n
      /\   /\
     a  j @  @
    /\ /\
    @@ i@
       /\
       @@

Qu'imprimerons-nous?

From k, we go left to
  h, where we go left to
    a, where we go left to 
      null, where we do nothing and so
    we return to a, where we print 'a' and then go right to
      null, where we do nothing and so
    we return to a and are done, so
  we return to h, where we print 'h' and then go right to
    j, where we go left to
      i, where we go left to 
        null, where we do nothing and so
      we return to i, where we print 'i' and then go right to
        null, where we do nothing and so
      we return to i and are done, so
    we return to j, where we print 'j' and then go right to
      null, where we do nothing and so
    we return to j and are done, so
  we return to h and are done, so
we return to k, where we print 'k' and then go right to
  n where we go left to 
    null, where we do nothing and so
  we return to n, where we print 'n' and then go right to
    null, where we do nothing and so
  we return to n and are done, so 
we return to k and are done, so we return to the caller

Donc, si nous regardons simplement les lignes, nous avons imprimé:

    we return to a, where we print 'a' and then go right to
  we return to h, where we print 'h' and then go right to
      we return to i, where we print 'i' and then go right to
    we return to j, where we print 'j' and then go right to
we return to k, where we print 'k' and then go right to
  we return to n, where we print 'n' and then go right to

Nous voyons que nous avons imprimé "ahijkn", qui est en effet par ordre alphabétique.

Nous parvenons à imprimer un arbre entier, par ordre alphabétique, simplement en sachant imprimer un seul nœud par ordre alphabétique. Ce qui était juste (parce que notre arbre avait la propriété spéciale de classer les valeurs à gauche des valeurs alphabétiques ultérieures) de savoir imprimer l'enfant gauche avant d'imprimer la valeur du nœud et d'imprimer l'enfant droit après avoir imprimé la valeur du nœud.

Et c'est le pouvoir de la récursivité: être capable de faire des choses entières en ne sachant que comment faire une partie de l'ensemble (et en sachant quand arrêter de récidiver).

Rappelant que dans la plupart des langues, l'opérateur || ("ou") court-circuits lorsque son premier opérande est vrai, la fonction récursive générale est:

void recurse() { doWeStop() || recurse(); } 

Luc M commente:

SO doit donc créer un badge pour ce type de réponse. Toutes nos félicitations!

Merci, Luc! Mais, en fait, parce que j'ai édité cette réponse plus de quatre fois (pour ajouter le dernier exemple, mais surtout pour corriger les fautes de frappe et les peaufiner - taper sur un minuscule clavier de netbook est difficile), je ne peux pas obtenir plus de points pour cela . Ce qui me décourage quelque peu de consacrer autant d'efforts aux réponses futures.

Voir mon commentaire ici à ce sujet: /programming/128434/what-are-community-wiki-posts-in-stackoverflow/718699#718699

Votre cerveau a explosé parce qu'il est entré dans une récursion infinie. C'est une erreur courante pour les débutants.

Croyez-le ou non, vous comprenez déjà la récursivité, vous êtes simplement entraîné par une métaphore commune, mais défectueuse pour une fonction: une petite boîte avec des trucs qui entrent et sortent.

Pensez à la place d'une tâche ou d'une procédure, comme "en savoir plus sur la récursivité sur le net". C'est récursif et cela ne vous pose aucun problème. Pour terminer cette tâche, vous pouvez:

a) Lisez la page de résultats de Google pour "récursivité"
b) Une fois que vous l'avez lu, suivez le premier lien dessus et ...
a.1) Lisez cette nouvelle page sur la récursivité 
b.1) Une fois que vous l'avez lu, suivez le premier lien dessus et ...
a.2) Lisez cette nouvelle page sur la récursivité 
b.2) Une fois que vous l'avez lu, suivez le premier lien dessus et ...

Comme vous pouvez le voir, vous faites des trucs récursifs depuis longtemps sans aucun problème.

Pendant combien de temps continueriez-vous à faire cette tâche? Toujours jusqu'à ce que votre cerveau explose? Bien sûr que non, vous vous arrêterez à un moment donné, chaque fois que vous pensez avoir terminé la tâche.

Il n'est pas nécessaire de spécifier cela lorsque vous vous demandez de "en savoir plus sur la récursivité sur le net", car vous êtes un humain et vous pouvez en déduire vous-même.

L'ordinateur ne peut pas déduire la prise, vous devez donc inclure une fin explicite: "en savoir plus sur la récursivité sur le net, JUSQU'À ce que vous le compreniez ou que vous ayez lu un maximum de 10 pages ".

Vous avez également déduit que vous devriez commencer sur la page de résultats de Google pour la «récursivité», et encore une fois, c'est quelque chose qu'un ordinateur ne peut pas faire. La description complète de notre tâche récursive doit également inclure un point de départ explicite:

"en savoir plus sur la récursivité sur le net, JUSQU'À ce que vous le compreniez ou que vous ayez lu un maximum de 10 pages et en commençant à www.google.com/search?q=recursion "

Pour grogner le tout, je vous suggère d'essayer l'un de ces livres:

• Common Lisp: A Gentle Introduction to Symbolic Computation. C'est l'explication non mathématique la plus mignonne de la récursivité.
• Le petit intrigant.

Pour comprendre la récursivité, il vous suffit de regarder sur l'étiquette de votre flacon de shampoing:

function repeat()
{
   rinse();
   lather();
   repeat();
}

Le problème est qu'il n'y a pas de condition de terminaison et que la récursivité se répétera indéfiniment, ou jusqu'à ce que vous manquiez de shampoing ou d'eau chaude (conditions de terminaison externes, similaires à souffler votre pile).

Si vous voulez un livre qui explique bien la récursivité en termes simples, jetez un œil à Gödel, Escher, Bach: An Eternal Golden Braid de Douglas Hofstadter, en particulier au chapitre 5. En plus de la récursivité, il explique bien un certain nombre de concepts complexes en informatique et en mathématiques d'une manière compréhensible, avec une explication s'appuyant sur une autre. Si vous n'avez pas été très exposé à ce genre de concepts auparavant, cela peut être un livre assez époustouflant.

Il s'agit plus d'une plainte que d'une question. Avez-vous une question plus spécifique sur la récursivité? Comme la multiplication, ce n'est pas une chose sur laquelle les gens écrivent beaucoup.

En parlant de multiplication, pensez-y.

Question:

Qu'est-ce qu'un * b?

Répondre:

Si b est 1, c'est a. Sinon, c'est a + a * (b-1).

Qu'est-ce qu'un * (b-1)? Voir la question ci-dessus pour un moyen de le résoudre.

Je pense que cette méthode très simple devrait vous aider à comprendre la récursivité. La méthode s'appellera jusqu'à ce qu'une certaine condition soit remplie, puis retournera:

function writeNumbers( aNumber ){
 write(aNumber);
 if( aNumber > 0 ){
  writeNumbers( aNumber - 1 );
 }
 else{
  return;
 }
}

Cette fonction imprimera tous les numéros du premier numéro que vous alimenterez jusqu'à 0. Ainsi:

writeNumbers( 10 );
//This wil write: 10 9 8 7 6 5 4 3 2 1 0
//and then stop because aNumber is no longer larger then 0

Ce qui se passe, c'est que writeNumbers (10) écrira 10 puis appellera writeNumbers (9) qui écrira 9 puis appellera writeNumber (8), etc. Jusqu'à writeNumbers (1) écrit 1 puis appelle writeNumbers (0) qui écrira 0 butt n'appellera pas writeNumbers (-1);

Ce code est essentiellement le même que:

for(i=10; i>0; i--){
 write(i);
}

Alors pourquoi utiliser la récursivité, vous pourriez demander, si une boucle for fait essentiellement la même chose. Eh bien, vous utilisez principalement la récursivité lorsque vous devez imbriquer des boucles mais ne savez pas à quelle profondeur elles sont imbriquées. Par exemple, lors de l'impression d'éléments à partir de tableaux imbriqués:

var nestedArray = Array('Im a string', 
                        Array('Im a string nested in an array', 'me too!'),
                        'Im a string again',
                        Array('More nesting!',
                              Array('nested even more!')
                              ),
                        'Im the last string');
function printArrayItems( stringOrArray ){
 if(typeof stringOrArray === 'Array'){
   for(i=0; i<stringOrArray.length; i++){ 
     printArrayItems( stringOrArray[i] );
   }
 }
 else{
   write( stringOrArray );
 }
}

printArrayItems( stringOrArray );
//this will write:
//'Im a string' 'Im a string nested in an array' 'me too' 'Im a string again'
//'More nesting' 'Nested even more' 'Im the last string'

Cette fonction pourrait prendre un tableau qui pourrait être imbriqué dans 100 niveaux, tandis que l'écriture d'une boucle for vous obligerait à l'imbriquer 100 fois:

for(i=0; i<nestedArray.length; i++){
 if(typeof nestedArray[i] == 'Array'){
  for(a=0; i<nestedArray[i].length; a++){
   if(typeof nestedArray[i][a] == 'Array'){
    for(b=0; b<nestedArray[i][a].length; b++){
     //This would be enough for the nestedAaray we have now, but you would have
     //to nest the for loops even more if you would nest the array another level
     write( nestedArray[i][a][b] );
    }//end for b
   }//endif typeod nestedArray[i][a] == 'Array'
   else{ write( nestedArray[i][a] ); }
  }//end for a
 }//endif typeod nestedArray[i] == 'Array'
 else{ write( nestedArray[i] ); }
}//end for i

Comme vous pouvez le voir, la méthode récursive est bien meilleure.

En fait, vous utilisez la récursivité pour réduire la complexité de votre problème. Vous appliquez la récursivité jusqu'à ce que vous atteigniez un cas de base simple qui peut être résolu facilement. Avec cela, vous pouvez résoudre la dernière étape récursive. Et avec cela, toutes les autres étapes récursives jusqu'à votre problème d'origine.

Je vais essayer de l'expliquer avec un exemple.

Tu sais quoi n! veux dire? Sinon: http://en.wikipedia.org/wiki/Factorial

3! = 1 * 2 * 3 = 6

voici un pseudocode

function factorial(n) {
  if (n==0) return 1
  else return (n * factorial(n-1))
}

Essayons donc:

factorial(3)

est n 0?

non!

nous creusons donc plus profondément avec notre récursivité:

3 * factorial(3-1)

3-1 = 2

est 2 == 0?

non!

nous allons donc plus loin! 3 * 2 * factoriel (2-1) 2-1 = 1

est 1 == 0?

non!

nous allons donc plus loin! 3 * 2 * 1 * factoriel (1-1) 1-1 = 0

est 0 == 0?

Oui!

nous avons un cas trivial

nous avons donc 3 * 2 * 1 * 1 = 6

j'espère que cela vous a aidé

Récursivité

La méthode A appelle la méthode A appelle la méthode A. Finalement, l'une de ces méthodes A n'appellera pas et ne quittera pas, mais c'est la récursivité car quelque chose s'appelle.

Exemple de récursivité où je veux imprimer chaque nom de dossier sur le disque dur: (en c #)

public void PrintFolderNames(DirectoryInfo directory)
{
    Console.WriteLine(directory.Name);

    DirectoryInfo[] children = directory.GetDirectories();

    foreach(var child in children)
    {
        PrintFolderNames(child); // See we call ourself here...
    }
}

Quel livre utilisez-vous?

Le manuel standard sur les algorithmes qui est vraiment bon est Cormen & Rivest. D'après mon expérience, il enseigne assez bien la récursivité.

La récursivité est l'une des parties les plus difficiles à comprendre de la programmation, et bien qu'elle nécessite un instinct, elle peut être apprise. Mais il a besoin d'une bonne description, de bons exemples et de bonnes illustrations.

De plus, 30 pages en général, c'est beaucoup, 30 pages dans un seul langage de programmation prêtent à confusion. N'essayez pas d'apprendre la récursivité en C ou Java, avant de comprendre la récursivité en général à partir d'un livre général.

Une fonction récursive est simplement une fonction qui s'appelle autant de fois qu'elle le doit. C'est utile si vous devez traiter quelque chose plusieurs fois, mais vous n'êtes pas sûr du nombre de fois qui sera réellement nécessaire. D'une certaine manière, vous pourriez considérer une fonction récursive comme un type de boucle. Comme une boucle, cependant, vous devrez spécifier les conditions de rupture du processus, sinon il deviendra infini.

http://javabat.com est un endroit amusant et excitant pour pratiquer la récursivité. Leurs exemples commencent assez légers et fonctionnent par le biais de vastes (si vous voulez aller aussi loin). Remarque: Leur approche est d'apprendre en pratiquant. Voici une fonction récursive que j'ai écrite pour remplacer simplement une boucle for.

La boucle for:

public printBar(length)
{
  String holder = "";
  for (int index = 0; i < length; i++)
  {
    holder += "*"
  }
  return holder;
}

Voici la récursivité pour faire la même chose. (notez que nous surchargeons la première méthode pour nous assurer qu'elle est utilisée comme ci-dessus). Nous avons également une autre méthode pour maintenir notre index (similaire à la façon dont l'instruction for le fait pour vous ci-dessus). La fonction récursive doit conserver son propre index.

public String printBar(int Length) // Method, to call the recursive function
{
  printBar(length, 0);
}

public String printBar(int length, int index) //Overloaded recursive method
{
  // To get a better idea of how this works without a for loop
  // you can also replace this if/else with the for loop and
  // operationally, it should do the same thing.
  if (index >= length)
    return "";
  else
    return "*" + printBar(length, index + 1); // Make recursive call
}

Pour faire court, la récursivité est un bon moyen d'écrire moins de code. Dans ce dernier printBar, notez que nous avons une instruction if. SI notre condition a été atteinte, nous quitterons la récursivité et reviendrons à la méthode précédente, qui revient à la méthode précédente, etc. Si j'ai envoyé un printBar (8), j'obtiens ********. J'espère qu'avec un exemple d'une fonction simple qui fait la même chose qu'une boucle for, cela peut peut-être aider. Vous pouvez cependant vous entraîner davantage sur Java Bat.

La manière véritablement mathématique d'envisager la création d'une fonction récursive serait la suivante:

1: Imaginez que vous ayez une fonction correcte pour f (n-1), construisez f de telle sorte que f (n) soit correcte. 2: Construisez f, de telle sorte que f (1) soit correct.

C'est ainsi que vous pouvez prouver que la fonction est correcte, mathématiquement, et elle s'appelle Induction . C'est équivalent d'avoir différents cas de base, ou des fonctions plus compliquées sur plusieurs variables). Il est également équivalent d'imaginer que f (x) est correct pour tous les x

Maintenant, pour un exemple "simple". Construisez une fonction qui peut déterminer s'il est possible d'avoir une combinaison de pièces de 5 cents et 7 cents pour faire x cents. Par exemple, il est possible d'avoir 17 cents par 2x5 + 1x7, mais impossible d'avoir 16 cents.

Imaginez maintenant que vous ayez une fonction qui vous indique s'il est possible de créer x cents, tant que x <n. Appelez cette fonction can_create_coins_small. Il devrait être assez simple d'imaginer comment faire la fonction pour n. Construisez maintenant votre fonction:

bool can_create_coins(int n)
{
    if (n >= 7 && can_create_coins_small(n-7))
        return true;
    else if (n >= 5 && can_create_coins_small(n-5))
        return true;
    else
        return false;
}

L'astuce consiste à réaliser que le fait que can_create_coins fonctionne pour n signifie que vous pouvez substituer can_create_coins à can_create_coins_small, donnant:

bool can_create_coins(int n)
{
    if (n >= 7 && can_create_coins(n-7))
        return true;
    else if (n >= 5 && can_create_coins(n-5))
        return true;
    else
        return false;
}

Une dernière chose à faire est d'avoir un cas de base pour arrêter la récursion infinie. Notez que si vous essayez de créer 0 cents, cela est possible en n'ayant pas de pièces. L'ajout de cette condition donne:

bool can_create_coins(int n)
{
    if (n == 0)
        return true;
    else if (n >= 7 && can_create_coins(n-7))
        return true;
    else if (n >= 5 && can_create_coins(n-5))
        return true;
    else
        return false;
}

Il peut être prouvé que cette fonction reviendra toujours, en utilisant une méthode appelée descente infinie , mais ce n'est pas nécessaire ici. Vous pouvez imaginer que f (n) n'appelle que des valeurs inférieures de n, et finira toujours par atteindre 0.

Pour utiliser ces informations pour résoudre votre problème de la Tour de Hanoi, je pense que l'astuce est de supposer que vous avez une fonction pour déplacer n-1 tablettes de a vers b (pour tout a / b), en essayant de déplacer n tables de a vers b .

Exemple récursif simple en Common Lisp :

MYMAP applique une fonction à chaque élément d'une liste.

1) une liste vide n'a pas d'élément, donc nous retournons la liste vide - () et NIL sont tous les deux la liste vide.

2) appliquer la fonction à la première liste, appeler MYMAP pour le reste de la liste (l'appel récursif) et combiner les deux résultats dans une nouvelle liste.

(DEFUN MYMAP (FUNCTION LIST)
  (IF (NULL LIST)
      ()
      (CONS (FUNCALL FUNCTION (FIRST LIST))
            (MYMAP FUNCTION (REST LIST)))))

Regardons l'exécution tracée. En entrant dans une fonction, les arguments sont imprimés. A la sortie d'une fonction, le résultat est imprimé. Pour chaque appel récursif, la sortie sera mise en retrait au niveau.

Cet exemple appelle la fonction SIN sur chaque numéro d'une liste (1 2 3 4).

Command: (mymap 'sin '(1 2 3 4))

1 Enter MYMAP SIN (1 2 3 4)
| 2 Enter MYMAP SIN (2 3 4)
|   3 Enter MYMAP SIN (3 4)
|   | 4 Enter MYMAP SIN (4)
|   |   5 Enter MYMAP SIN NIL
|   |   5 Exit MYMAP NIL
|   | 4 Exit MYMAP (-0.75680256)
|   3 Exit MYMAP (0.14112002 -0.75680256)
| 2 Exit MYMAP (0.9092975 0.14112002 -0.75680256)
1 Exit MYMAP (0.841471 0.9092975 0.14112002 -0.75680256)

Voici notre résultat :

(0.841471 0.9092975 0.14112002 -0.75680256)

Pour expliquer la récursivité à un enfant de six ans, expliquez-la d'abord à un enfant de cinq ans, puis attendez un an.

En fait, c'est un contre-exemple utile, car votre appel récursif devrait être plus simple, pas plus difficile. Il serait encore plus difficile d'expliquer la récursivité à un enfant de cinq ans, et bien que vous puissiez arrêter la récursivité à 0, vous n'avez pas de solution simple pour expliquer la récursivité à un enfant de zéro an.

Pour résoudre un problème à l'aide de la récursivité, sous-divisez-le d'abord en un ou plusieurs problèmes plus simples que vous pouvez résoudre de la même manière, puis lorsque le problème est assez simple à résoudre sans récursivité supplémentaire, vous pouvez revenir à des niveaux supérieurs.

En fait, c'était une définition récursive de la façon de résoudre un problème de récursivité.

Les enfants utilisent implicitement la récursivité, par exemple:

Road trip à Disney World

Sommes-nous encore là? (Non)

Sommes-nous encore là? (Bientôt)

Sommes-nous encore là? (Presque ...)

Sommes-nous encore là? (SHHHH)

Sommes-nous déjà là?(!!!!!)

À quel moment l'enfant s'endort ...

Cette fonction de compte à rebours est un exemple simple:

function countdown()
      {
      return (arguments[0] > 0 ?
        (
        console.log(arguments[0]),countdown(arguments[0] - 1)) : 
        "done"
        );
      }
countdown(10);

La loi de Hofstadter appliquée aux projets logiciels est également pertinente.

L'essence du langage humain est, selon Chomsky, la capacité des cerveaux finis à produire ce qu'il considère comme des grammaires infinies. Par cela, il veut dire non seulement qu'il n'y a pas de limite supérieure à ce que nous pouvons dire, mais qu'il n'y a pas de limite supérieure sur le nombre de phrases de notre langue, il n'y a pas de limite supérieure sur la taille d'une phrase particulière. Chomsky a affirmé que l'outil fondamental qui sous-tend toute cette créativité du langage humain est la récursivité: la capacité d'une phrase à se reproduire à l'intérieur d'une autre phrase du même type. Si je dis "la maison du frère de John", j'ai un nom, "maison", qui se produit dans une phrase substantielle, "la maison du frère", et cette phrase nominale se produit dans une autre phrase substantielle, "la maison du frère de John". Cela a beaucoup de sens, et c'est '

Références

• Récursivité et pensée humaine

Lorsque je travaille avec des solutions récursives, j'essaie toujours de:

• Établir d'abord le cas de base, c'est-à-dire lorsque n = 1 dans une solution à factorielle
• Essayez de trouver une règle générale pour tous les autres cas

Il existe également différents types de solutions récursives, il y a l'approche diviser pour mieux régner qui est utile pour les fractales et bien d'autres.

Il serait également utile de commencer par résoudre des problèmes plus simples simplement pour comprendre. Quelques exemples résolvent la factorielle et génèrent le nième nombre de fibonacci.

Pour les références, je recommande fortement les algorithmes de Robert Sedgewick.

J'espère que cela pourra aider. Bonne chance.

Aie. J'ai essayé de comprendre les tours de Hanoi l'année dernière. La chose délicate à propos de TOH n'est pas un simple exemple de récursivité - vous avez des récursions imbriquées qui changent également les rôles des tours à chaque appel. La seule façon de lui donner un sens était de visualiser littéralement le mouvement des anneaux dans mon esprit et de verbaliser ce que serait l'appel récursif. Je commencerais par un seul anneau, puis deux, puis trois. J'ai en fait commandé le jeu sur Internet. Il m'a fallu peut-être deux ou trois jours pour me casser la tête pour l'obtenir.

Une fonction récursive est comme un ressort que vous compressez un peu à chaque appel. À chaque étape, vous mettez un peu d'informations (contexte actuel) sur une pile. Lorsque l'étape finale est atteinte, le ressort est libéré, collectant toutes les valeurs (contextes) à la fois!

Pas sûr que cette métaphore soit efficace ... :-)

Quoi qu'il en soit, au-delà des exemples classiques (factorielle qui est le pire exemple car elle est inefficace et facilement aplatie, Fibonacci, Hanoi ...) qui sont un peu artificielles (je les utilise rarement, voire jamais, dans de vrais cas de programmation), c'est intéressant de voir où il est vraiment utilisé.

Un cas très courant consiste à parcourir un arbre (ou un graphique, mais les arbres sont plus courants, en général).
Par exemple, une hiérarchie de dossiers: pour lister les fichiers, vous les parcourez. Si vous trouvez un sous-répertoire, la fonction listant les fichiers s'appelle avec le nouveau dossier comme argument. En revenant de lister ce nouveau dossier (et ses sous-dossiers!), Il reprend son contexte, dans le fichier (ou dossier) suivant.
Un autre cas concret est lors du dessin d'une hiérarchie de composants GUI: il est courant d'avoir des conteneurs, comme des volets, pour contenir des composants qui peuvent également être des volets, ou des composants composés, etc. La routine de peinture appelle récursivement la fonction de peinture de chaque composant, qui appelle la fonction de peinture de tous les composants qu'il contient, etc.

Je ne sais pas si je suis très clair, mais j'aime montrer l'utilisation du matériel pédagogique dans le monde réel, car c'était quelque chose sur lequel je suis tombé par le passé.

Pensez à une abeille ouvrière. Il essaie de faire du miel. Il fait son travail et attend que d'autres abeilles ouvrières fassent le reste du miel. Et quand le nid d'abeille est plein, il s'arrête.

Pensez-le comme magique. Vous avez une fonction qui porte le même nom que celle que vous essayez d'implémenter et quand vous lui donnez le sous-problème, elle la résout pour vous et la seule chose que vous devez faire est d'intégrer la solution de votre pièce avec la solution qu'elle vous a donné.

Par exemple, nous voulons calculer la longueur d'une liste. Appelons notre fonction magical_length et notre assistant magique avec magical_length Nous savons que si nous donnons la sous-liste qui n'a pas le premier élément, cela nous donnera la longueur de la sous-liste par magie. Ensuite, la seule chose que nous devons penser est de savoir comment intégrer ces informations à notre travail. La longueur du premier élément est 1 et magic_counter nous donne la longueur de la sous-liste n-1, donc la longueur totale est (n-1) + 1 -> n

int magical_length( list )
  sublist = rest_of_the_list( list )
  sublist_length = magical_length( sublist ) // you can think this function as magical and given to you
  return 1 + sublist_length

Cependant, cette réponse est incomplète car nous n'avons pas considéré ce qui se passe si nous donnons une liste vide. Nous pensions que la liste que nous avons comportait toujours au moins un élément. Par conséquent, nous devons réfléchir à ce que devrait être la réponse si on nous donne une liste vide et la réponse est évidemment 0. Donc, ajoutez ces informations à notre fonction et cela s'appelle la condition de base / bord.

int magical_length( list )
  if ( list is empty) then
    return 0
  else
    sublist_length = magical_length( sublist ) // you can think this function as magical and given to you
    return 1 + sublist_length