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.
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), soit 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 fatiguant 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 -
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). Voici une représentation arborescente de la 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'arbre 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é 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. Prenons un tableau fib [] où nous stockons les solutions de sous-tâches précédemment résolues. Nous savons déjà que fib [0] = 0 et fib [1] = 1. Stockons ces deux valeurs. Maintenant, quelle est la valeur de fib [2]? Comme fib [0] = 0 et fib [1] = 1 ont déjà été stockés, il suffit de dire fib [2] = fib [1] + fib [0] et c'est tout. On peut générer fib [3], fib [4], fib [5], ……, fib [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 ne soit pas résolue, ce qui réduit le calcul redondant.
