Рекурсивні функції і алгоритми представлення і обчислення

Функція рекурсивна, якщо або , при цьому може бути, що . 4

Рекурсивний процес обчислення алгоритмічно можна задати явно і неявно циклічно. У програмуванні за допомогою операторів циклів, або рекурсивною процедурою.

У програмуванні при обчислені функцій надається перевага рекурсивним процедурам.

Розглянемо приклад обчислення числової функції . При умові .

Схематичний фрагмент рекурсивного обчислення факторіала можна записати через повторення операції множення

long f(int n)

{

if (n < 0) return 0;

if (n == 0) return 1;

return n * f(n-1);

}.

У математичному забезпечені середовищ програмування обробка масивів, списків, дерев, трансцендентних функцій і інш., виконується рекурсивно. 5

Наприклад, функції , ,

можливо обчислити безпосередньо за наведеними рядами, але для цього необхідно організувати дві рекурсії і прямий цикл, що недоцільно. Тому, що можна організувати одну рекурсію.

За схемою Горнера: ,

тоді за правилом , можна створити рекурсивний процес (процедура) обчислення функції.

Однак, процедура обчислення трансцендентних функцій за допомогою рядів, також не доречна. Пояснимо це на прикладі функції , яка представляється рядом , , у якому абсолютна величина чисел Бернуллі

. 6

Зрозуміло, що обчислення функції у такий спосіб складно. Тому обчислення цієї функції краще виконувати за формулою , у якій ряди для функцій і одно типові, і можна організувати один рекурсивний процес, з якого вибирати необхідні значення для по черзі для функцій і .

Однак ситуація покращується, скористатися представленням функції ланцюговим дробом:

Зауважимо, що від ланцюгового дробу легко перейти до ряду, але перехід від ряду до дробу це мистецтво.

Особливості ланцюгових дробів:

- їх простота, 7

- рекурсивне представлення і обчислення,

- оптимальна кількість операцій і їх типізація.

Так у наведеному дробу явно використовується дві операції: віднімання і ділення та одна неявна операція складання.

Школа Лебєдєва С.А. використовувала ланцюгові дроби у 60 роках попереднього століття, а американці тільки тепер.