Рекурсия

 

Рекурсивная функция – это такая функция, которая вызывает сама себя в момент ее создания. Рекурсия – очень мощный и удобный инструмент решения задач. Так, например, один из самых быстрых алгоритмов сортировки массива использует рекурсию. Вычислить детерминант квадратной матрицы также помогает рекурсия и т.д.

Числа Фибоначчи, которые связаны с условными кроликами:

Поколение кроликов	...									...
Число кроликов	...

 

Приведенный ряд специально начат не с традиционного места (первое поколение), а с четвертого поколения (три кролика), для того чтобы задать читателю вопрос, подобный тому, который стоял в задаче о факториале: «Чему равно минимальное число кроликов в популяции – каково наименьшее число Фибоначчи?» Нормальный ответ, приводимый во всех учебниках, – ноль. Но не будем спешить и напишем программу с двусторонней рекурсией, взяв за базовые числа Фибоначчи не традиционную пару 0 и 1, а 13 и 21.

Рис. 4.3 - Расчет чисел Фибоначчи (двусторонняя рекурсия)

 

Ряд кроликов Фибоначчи в «отрицательных поколениях» зеркально отображает значения в «положительных поколениях», но с переменным знаком.

Числа Фибоначчи в наше время широко применяются в вычислительной математике, в том числе и для иллюстрации рекурсии.

Рис. 4.4 - Расчет изящных чисел Фибоначчи (двусторонняя рекуррентность)

Использование рекурсии для поиска чисел Фибоначчи – это стрельба из пушки по воробьям. Намного эффективнее рассчитывать подобные числа в цикле, рекуррентно. На рис. 4.4 представлена программа, по которой ищутся, если так можно выразиться, изящные (fine) числа Фибоначчи.