Fib1=1; Fib2=2.
Fib1=1; Fib2=2.
Рекурсивный вариант программируется здесь “в лоб”, без малейших усилий:
function Fib (n : byte) : longint;
begin
case n of
1: Fib := 1;
2: Fib := 2
else Fib := Fib (n-2) + Fib (n-1)
end
End;
- но стоит внимательнее проанализировать хотя бы небольшой (n=5) тестовый пример, иллюстрирующий последовательные состояния стека, и недостатки сразу проявляются. Если вам прежде не приходилось с этим контрпримером сталкиваться, - стоит выполнить
Упражнение #1.
a)
Установите, сколько всего вызовов функции Fib понадобится и будет помещено в стек при n=5. То же - при произвольном значении n.
b)
Сколько будет “лишних” вызовов, то есть дублирующих ранее осуществленные? Попробуйте вывести соответствующую зависимость для произвольного значения n.
Позднее мы еще вернемся к этому примеру. Пока же - несколько упражнений на использование рекурсии.
Упражнение #2.
a)
Напишите и сравните, с точки зрения отмеченных выше различий, рекурсивный и нерекурсивный
Индекс
Элементарные функции
Линейные уравнения
Нелинейные уравнения
Случайные числа
