Послідовність Фібоначчі - це, за визначенням, цілочисельна послідовність, в якій кожне число після перших двох є сумою двох попередніх чисел. Для спрощення:
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 ++ (найважчий). Але це залежить від вашої особистої думки та вашого досвіду роботи з кожною мовою.
Сподіваюся, вам сподобалась ця стаття, і якщо у вас є якісь запитання / рекомендації або просто ви хочете привітатись, коментуйте нижче!