Реалити о ЕГЭ

Рекурсия

Рекурсия в общем смысле — это вызов функцией самой себя.

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

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

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

Последовательность Фибоначчи представляет следующий ряд чисел: 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;

Если вы нашли ошибку, пожалуйста, выделите фрагмент текста и нажмите Ctrl+Enter. Мы обязательно поправим!

Редакция Без Сменки
Честно. Понятно. С душой.
Где вы учитесь?

Вам так же будет интересно

Как проходят выборы и все ли обладают избирательным правом?
Каждый из нас обладает равным избирательным правом в пределах своего избирательного округа. И...
Правление Александра III
💥1 марта 1881 года было совершено последнее покушение на Александра II. Нападение совершила...
Основные тригонометрические тождества
Подготовили основные тригонометрические тождества, которые нужно знать для ЕГЭ по математике: ...
Спряжение глагола
Сегодня мы с тобой вспомним виды спряжение глагола и как его определить 🙊 Существует два вида...
Поздравления на английском
Итак, давай начнём с того, как поздравить своего краша:😍 ♦️My soulmate, I wish you a happy New...
Сквозная тема
Давай вернемся в детский сад. Садись за стол, бери вот эту коробку. Смотри, как много в ней разных...

0 комментария

Авторизуйтесь, чтобы оставить комментарий.

Подпишитесь на еженедельную рассылку полезных материалов про ЕГЭ, высшее образование и вузы и получите скидку на курсы Вебиума

Сообщить об опечатке

Текст, который будет отправлен нашим редакторам: