Пример «Числа Фибоначчи»

Файлы:

Пример программы на языке программирования Перфо:

//Эта программа написана на языке программирования Перфо
//для демонстрации написания функций и рекурсии 


//Вычисление чисел Фибоначчи реализуем с помощью рекурсии

//Способ 1:
//рекурсия в виде дерева... дерево вызовов очень быстро растет...
(функция (Фибоначчи Н)
  (Выбор ((= Н 0) 0)
        ((= Н 1) 1)
        (Иначе (+ (Фибоначчи (- Н 1)) (Фибоначчи (- Н 2))))
  )
)
//тест
(Для (Инд 0 10)
    (Вывод "Результат (Фибоначчи " Инд ") = " (Фибоначчи Инд) ПС)
) 
(Вывод пс)

//Способ 2:
//заменяем рекурсию в виде дерева на линейную рекурсию,
//что намного эффективнее
(функция (Фибоначчи2 Н) 
  (Фибоначчи2-итерация 1 0 Н))

(функция (Фибоначчи2-итерация А Б Счетчик)
  (Если (= Счетчик 0)
      Б
      (Фибоначчи2-итерация (+ А Б) А (- Счетчик 1))))
//тест
(Для (Инд 0 10)
    (Вывод "Результат (Фибоначчи2 " Инд ") = " (Фибоначчи2 Инд) ПС)
) 
(Вывод пс)

//Способ 3:
//заменяем рекурсию на цикл,
//что ещё эффективнее, чем линейная рекурсия
(функция (Фибоначчи3 Н)
    (Перем Чис1 0)
    (Перем Чис2 0)
    (Перем Рез 0)
    (Для (Инд 1 Н)
        (Если (Или (= Инд 1) (= Инд 2)) 
            (Уст Рез 1)
            (Уст Рез (+ Чис1 Чис2))
        )
        (Уст Чис1 Чис2)
        (Уст Чис2 Рез)
    )
    Рез
)
//тест
(Для (Инд 0 10)
    (Вывод "Результат (Фибоначчи3 " Инд ") = " (Фибоначчи3 Инд) ПС)
) 
(Вывод пс)

К началу статьи