Статья Автор: Деникина Н.В., Деникин А.В.

Вопрос 16. Рекурсия (Python). Общие сведения

Рекурсивные функции

Чтобы написать рекурсивную функцию, необходимо определить:
1) Базовый случай - условие окончания рекурсии. Другими словами определить при каком условии рекурсивная функция заверает свою работу.
2) Рекурсвный случай, описанный с помощью реккуррентного соотношения. Рекуррентные соотношения описывают как следующее значение в последовательности зависит от предыдущих значений. 
Например, функция для вычисления чисел Фибоначчи может быть написана с использованием рекурсии, чтобы вычислить каждое число, используя рекуррентное соотношение \(F(n)=F(n-1)+F(n-2)\).

 


Пример 1

Алгоритм вычисления функции F(n) задан следующими соотношениями:

F(n) = n при n ≤ 3
F(n) = F(n–3) + F(n/3) + n, если n > 3 и  кратно трём,
F(n) = F(n–1) + F(n–2), если n > 3 и не кратно трём.


Чему равно значение функции F(50) + F(65)
Знак / обозначает операцию целочисленного деления.

Решить данное задание проще всего с использованием программы. Необходимо просто переписать данное рекуррентное соотношение в виде рекурсивной функции. 
Базовым случаем является случай, когда n ≤ 3, в этом случае функция должна вернуть просто значение n.
Две другие строчки: вычисляющие F(n), будут рекурсивными случаями, когда мы будем вызывать саму функцию с другими параметрами, зависящими от предыдущих и возвращать результат вычисления. 
Основная программа будет вызывать рекурсивную функцию со значением F(50) и F(65). Результаты вычисления функции с этими параметрами складываются и выводится на экран.

Пропустить Навигационные Ссылки.
Чтобы оставить комментарий нужна авторизация
Печать