Comprendre la récursivité et la formule récursive

Itération

L’itération est la répétition d’un processus. Un étudiant qui va à l’école répète le processus d’aller à l’école tous les jours jusqu’à l’obtention de son diplôme. Nous allons à l’épicerie au moins une ou deux fois par mois pour acheter des produits. Nous répétons ce processus tous les mois. En mathématiques, une séquence de Fibonacci suit également les propriétés de la répétition des tâches. Considérons la séquence de Fibonacci où les deux premiers nombres sont 0 et 1, tous les autres nombres sont la somme des deux nombres précédents.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89

Étapes d’itération

La formule de Fibonacci peut être écrite comme suit:

F (n) = F (n – 1) + F (n – 2)
fibonacci (0) = 0
fibonacci (1) = 1
fibonacci (2) = fibonacci (1) + fibonacci (0) = 1 + 0 = 1
fibonacci (3) = fibonacci (2) + fibonacci (1) = 1 + 1 = 2
fibonacci (4) = fibonacci (3) + fibonacci (2) = 2 + 1 = 3
fibonacci (5) = fibonacci (4) + fibonacci (3) = 3 + 2 = 5
fibonacci (6) = fibonacci (5) + fibonacci (4) = 5 + 3 = 8

L’algorithme donné ci-dessous renvoie le nième nombre de Fibonacci.

fibonacci

Récursion

Chaque fois que nous obtenons un nouveau nombre de Fibonacci (nième nombre), ce nième nombre est en fait le (n – 1) e nombre lorsque nous trouvons (n ​​+ 1) e Fibonacci comme notre nième prochain Fibonacci. Comme nous le voyons les étapes d’itération mentionnées ci-dessus: si n = 2 alors
fibonacci (2) = fibonacci (2 – 1) + fibonacci (2 – 2) = fibonacci (1) + fibonacci (0) = 1 + 0 = 1

Maintenant, nous voulons générer fibonacci (3), c’est-à-dire n = 3.

fibonacci (3) = fibonacci (3 – 1) + fibonacci (3 – 2) = fibonacci (2) + fibonacci (1) = 1 + 1 = 2
Cela signifie que chaque fois que n augmente la valeur du courant (n – 1) th et (n – 2) th fibonacci augmente également. Mais il est fatigant de garder une trace de (n – 1) ème et (n – 2) ème fibonacci pour chaque n. Que diriez-vous d’écrire une méthode qui s’appelle elle-même pour répéter la tâche d’itération par elle-même?

Une méthode qui s’appelle elle-même est nommée méthode récursive. Une méthode récursive doit avoir un cas de base où le programme cesse de s’appeler. Notre cas de base pour la série de Fibonacci est fibonacci (0) = 0 et fibonacci (1) = 1. Sinon, la méthode de Fibonacci s’appelle deux fois – fibonacci (n – 1) et fibonacci (n – 2). Ensuite, il les ajoute pour obtenir fibonacci (n). Une méthode récursive pour trouver le nième Fibonacci peut être écrite comme –

fibonacci2

Si nous regardons attentivement, la récursivité suit la propriété de stack. Il résout des sous-problèmes plus petits pour obtenir la solution d’un problème. Pour n> 1, il exécute la dernière ligne. Donc, si n = 6, la fonction appelle et ajoute fibonacci (6 – 1) et fibonacci (6 – 2). fibonacci (6 – 1) ou fibonacci (5) appelle et ajoute fibonacci (5 – 1) et fibonacci (5 – 2). Cette récursion continue jusqu’à ce que 6 atteigne sa valeur de cas de base qui est fibonacci (0) = 0 ou fibonacci (1) = 1. Une fois qu’il atteint le cas de base, il ajoute deux valeurs de base et augmente jusqu’à obtenir la valeur de fibonacci ( 6). Vous trouverez ci-dessous une représentation arborescente de la récursivité.

Arbre de récursivitéArbre de récursivité

Comme nous pouvons le voir, à quel point une récursivité peut être puissante. Une seule ligne de code crée l’arborescence ci-dessus (dernière ligne du code ci-dessus, y compris les cas de base). La récursivité maintient une pile et elle va plus loin jusqu’à ce qu’elle atteigne le cas de base. Programmation dynamique (DP): La récursivité est facile à comprendre et à coder mais peut être coûteuse en termes de temps et de mémoire. Jetez un œil à l’arbre de récursivité ci-dessous. Le sous-arbre gauche commençant par fib (4) et le sous-arbre droit commençant par fib (4) sont exactement les mêmes. Ils génèrent le même résultat qui est de 3 mais effectuent la même tâche deux fois. Si n est un grand nombre (exemple: 500000), la récursivité peut rendre un programme très lent car il appellerait la même sous-tâche plusieurs fois.

récursion entourée d'arbresrécursion entourée d’arbres

Pour éviter ce problème, la programmation dynamique peut être utilisée. En programmation dynamique, nous pouvons utiliser une sous-tâche précédemment résolue pour résoudre une tâche future du même type. C’est un moyen de réduire la tâche pour résoudre le problème d’origine. Ayons un tableau fib[] où nous stockons les solutions de sous-tâches précédemment résolues. Nous savons déjà ce mensonge[0] = 0 et fib[1] = 1. Stockons ces deux valeurs. Maintenant, quelle est la valeur du fib[2]? Comme mensonge[0] = 0 et fib[1] = 1 a déjà été stocké, il suffit de dire fib[2] = fib[1] + mensonge[0] et c’est tout. Nous pouvons générer des fib[3], mensonge[4], mensonge[5], ……, mensonge[n] de la même manière. Les sous-tâches précédemment résolues sont appelées pour obtenir la sous-tâche suivante jusqu’à ce que la tâche d’origine n’ait pas été résolue, ce qui réduit le calcul redondant.

fibonacci3

Similar Posts

Leave a Reply

Your email address will not be published. Required fields are marked *