La séquence de Fibonacci - expliquée en Python, JavaScript, C ++, Java et Swift

La séquence de Fibonacci est, par définition, la séquence d'entiers dans laquelle chaque nombre après les deux premiers est la somme des deux nombres précédents. Pour simplifier:

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

Il a de nombreuses applications en mathématiques et même en trading (oui, vous avez bien lu: trading), mais ce n'est pas le but de cet article. Mon objectif aujourd'hui est de vous montrer comment vous pouvez calculer n'importe quel terme de cette série de nombres dans cinq langages de programmation différents à l'aide de fonctions récursives.

Les fonctions récursives sont les fonctions qui, fondamentalement, s'appellent elles-mêmes.

Je tiens à noter que ce n'est pas la meilleure méthode pour le faire - en fait, cela pourrait être considéré comme la méthode la plus basique à cette fin. En effet, la puissance de calcul nécessaire pour calculer des termes plus grands de la série est immense. Le nombre d'appels de la fonction entraîne un débordement de pile dans la plupart des langues.

Tout de même, pour les besoins de ce tutoriel, commençons.

Tout d'abord, réfléchissons à ce à quoi le code va ressembler. Cela comprendra:

· Une fonction récursive F (F pour Fibonacci): pour calculer la valeur du terme suivant.

· Rien d'autre: je vous avais prévenu que c'était assez basique.

Notre fonction prendra n comme entrée, qui se référera au n ème terme de la séquence que nous voulons calculer. Ainsi, F (4) doit renvoyer le quatrième terme de la séquence.

Planifions-le. Le code doit, quelle que soit la langue, ressembler à ceci:

function F(n)  if n = 0

   return 0  if n = 1

   return 1  else

   return F(n-1) + F(n-2)

Remarque: le terme 0 de la séquence sera considéré comme 0, donc le premier terme sera 1; le second, 1; le troisième, 2; etc. Vous comprenez.

Analysons la fonction pendant un moment. S'il obtient 0 comme entrée, il renvoie 0. S'il obtient 1, il renvoie 1. S'il obtient 2… Eh bien, dans ce cas, il tombe dans l'instruction else, qui appellera à nouveau la fonction pour les termes 2–1 ( 1) et 2–2 (0). Cela renverra 1 et 0, et les deux résultats seront ajoutés, renvoyant 1. Parfait.

Vous pouvez maintenant voir pourquoi les fonctions récursives sont un problème dans certains cas. Imaginez que vous vouliez le 100e terme de la séquence. La fonction s'appellerait elle-même pour le 99e et le 98e, qui appelleraient eux-mêmes la fonction pour les 98e et 97e, et 97e et 96e trimestres… et ainsi de suite. Ce serait vraiment lent.

Mais la bonne nouvelle est que cela fonctionne réellement!

Commençons donc par les différentes langues. Je ne donnerai pas trop de détails (en fait, aucun détail) pour améliorer votre expérience de lecture. Il n'y a pas trop de détails de toute façon.

Allons-y:

Python

def F(n):  if n == 0:

   return 0  if n == 1:

   return 1  else:

   return F(n-1) + F(n-2)

Rapide

func F(_ n: Int) -> Int {  if n == 0 {    return 0

 }  if n == 1 {    return 1

 }  else {    return F(n-1) + F(n-2)

 }}

JavaScript

function F(n) {  if(n == 0) {    return 0;

 }  if(n == 1) {    return 1;

 }  else {    return F(n-1) + F(n-2);

 }}

Java

public static int F(int n) {  if(n == 0) {    return 0;

 }  if(n == 1) {    return 1;

 }  else {    return F(n-1) + F(n-2);

 }}

C ++

int F(int n) {  if(n == 0) {    return 0;

 }  if(n == 1) {    return 1;

 }  else {    return F(n-1) + F(n-2);

 }}

Et c'est tout. J'ai choisi ces langues uniquement en fonction de leur popularité - ou du moins parce que ce sont les 5 langues les plus courantes que j'utilise. Ils pourraient être classés par difficulté de syntaxe, à mon avis, de Python (le plus simple) au C ++ (le plus difficile). Mais cela dépend de votre opinion personnelle et de votre expérience avec chaque langue.

J'espère que cet article vous a plu et, si vous avez des questions / recommandations ou si vous voulez simplement dire bonjour, commentez ci-dessous!