Рекурсия

Как такое возможно? А что мешает те же операции выполнить ещё раз? Возможно, с другими условиями.

Сегодня правда обойдёмся без программирования 🙃

◾️Вычисление числа Фибоначчи

Последовательность Фибоначчи представляет следующий ряд чисел: 0,1,1,2,3,5,8,13,21,34,55,89.., в которой первые два числа равны либо 1 и 1, либо 0 и 1, а каждое последующее число равно сумме двух предыдущих чисел.

Для реализации рекурсивного вычисления таких чисел достаточно написать соотношение чисел и аккуратно запрограммировать:

F0=0, F1=1, при n>1 число Фибоначчи с номером n вычисляется как Fn=Fn−1+Fn−2

def Fib(n):#функция для вычисления нового члена последовательности
if n <= 1:# число на 0 и 1 месте=само число
return n#возвращаем число
else:#числа на остальных местах вычисляются как сумма 2-х предыдущих
return Fib(n — 1) + Fib(n — 2)#возвращаем число

print(Fib(10))#определяем число на 10ом месте — результат 55

Часто использование рекурсивных алгоритмов приводит к ошибкам. Например, может случиться бесконечная рекурсия, когда программа продолжает свою работу пока не кончится свободная память. Нередко причиной такой проблемы является неверное условие выхода из рекурсии:
допустим, в нашей программе мы забыли поставить проверку на первые 2 члена последовательности, тогда программа при параметре 1 будет вызывать 0, а потом пойдет вызов -1 и тд….

Поэтому перед написанием программы с рекурсией обязательно обрати внимания на условия, когда твой алгоритм успешно завершит свою работу.

Рекуррентные формулы:
F(n) = F(n-1)*2, при n>1;
F(n) = 1, при n = 1;
F(n) задана для натуральных n

Чему равна F(5)?
F(5) = F(4)*2 = F(3)*2*2 = F(2)*2*2*2 = F(1)*2*2*2*2 = 1*2*2*2*2 = 16 — это было несложно.

А если так?
F(n) = F(n-1)*3 + F(n-2)*2 , n>2;
F(2) = 2;
F(1) = 1;

Найти F(5)…

Тут без хорошего методa не обойдёшься. Давай решать просто с начала:
F(3) = 2*3 + 1*2=8;
F(4) = 8*3 + 2*2 = 28;
F(5) = 28*3 + 8*2 = 100;