Послідовність Фібоначчі - пояснюється на Python, JavaScript, C ++, Java та Swift

Послідовність Фібоначчі - це, за визначенням, цілочисельна послідовність, в якій кожне число після перших двох є сумою двох попередніх чисел. Для спрощення:

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

У ньому є багато застосувань у математиці та навіть у торгівлі (так, ви правильно прочитали: торгівля), але це не суть цієї статті. Моя сьогоднішня мета - показати вам, як можна обчислити будь-який доданок цієї серії чисел у п’яти різних мовах програмування за допомогою рекурсивних функцій.

Рекурсивні функції - це ті функції, які в основному називають себе.

Хочу зазначити, що це не найкращий метод для цього - насправді це можна вважати найосновнішим методом для цієї мети. Це пояснюється тим, що обчислювальна потужність, необхідна для обчислення більших термінів серії, величезна. Кількість викликів функції викликає переповнення стека в більшості мов.

Все-таки для цілей цього підручника почнемо.

Перш за все, давайте подумаємо, як буде виглядати код. Він включатиме:

· Рекурсивна функція F (F для Фібоначчі): для обчислення значення наступного доданка.

· Нічого іншого: я попередив вас, що це зовсім елементарно.

Наша функція прийме n як вхідні дані, які будуть посилатися на n- й член послідовності, яку ми хочемо обчислити. Отже, F (4) повинен повернути четвертий доданок послідовності.

Давайте це планувати. Код, незалежно від мови, повинен виглядати приблизно так:

function F(n)  if n = 0

   return 0  if n = 1

   return 1  else

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

Примітка: термін 0 послідовності вважатиметься 0, тому перший доданок буде 1; другий, 1; третя, 2; і так далі. Ви отримаєте його.

Давайте проаналізуємо функцію на мить. Якщо він отримує 0 як вхід, він повертає 0. Якщо він отримує 1, він повертає 1. Якщо він отримує 2 ... Ну, в такому випадку він потрапляє в оператор else, який знову викликає функцію на умовах 2–1 ( 1) та 2–2 (0). Це поверне 1 і 0, а два результати будуть додані, повернувши 1. Ідеально.

Тепер ви можете зрозуміти, чому рекурсивні функції в деяких випадках є проблемою. Уявіть, що ви хотіли 100-й член послідовності. Функція буде називати себе для 99-го та 98-го, які самі знову викликатимуть функцію для 98-го та 97-го, 97-го та 96-го доданків ... і так далі. Це було б дуже повільно.

Але хороша новина полягає в тому, що це насправді працює!

Тож давайте почнемо з різних мов. Я не буду надавати занадто багато деталей (насправді, взагалі ніяких деталей), щоб покращити ваш досвід читання. У будь-якому випадку немає занадто багато деталей.

Давайте скочимо в нього:

Python

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

   return 0  if n == 1:

   return 1  else:

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

Стрімкий

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);

 }}

І це все. Я вибрав ці мови, виходячи лише з популярності - або хоча б тому, що ці 5 найпоширеніших, якими я користуюсь. На мою думку, їх можна класифікувати за труднощами синтаксису від Python (найпростіший) до C ++ (найважчий). Але це залежить від вашої особистої думки та вашого досвіду роботи з кожною мовою.

Сподіваюся, вам сподобалась ця стаття, і якщо у вас є якісь запитання / рекомендації або просто ви хочете привітатись, коментуйте нижче!