КАТЕГОРИИ:
АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
|
Рекурсивні функції і алгоритми представлення і обчисленняФункція рекурсивна, якщо або , при цьому може бути, що . 4 Рекурсивний процес обчислення алгоритмічно можна задати явно і неявно циклічно. У програмуванні за допомогою операторів циклів, або рекурсивною процедурою. У програмуванні при обчислені функцій надається перевага рекурсивним процедурам. Розглянемо приклад обчислення числової функції . При умові . Схематичний фрагмент рекурсивного обчислення факторіала можна записати через повторення операції множення long f(int n) { if (n < 0) return 0; if (n == 0) return 1; return n * f(n-1); }.
У математичному забезпечені середовищ програмування обробка масивів, списків, дерев, трансцендентних функцій і інш., виконується рекурсивно. 5 Наприклад, функції , , можливо обчислити безпосередньо за наведеними рядами, але для цього необхідно організувати дві рекурсії і прямий цикл, що недоцільно. Тому, що можна організувати одну рекурсію. За схемою Горнера: , тоді за правилом , можна створити рекурсивний процес (процедура) обчислення функції. Однак, процедура обчислення трансцендентних функцій за допомогою рядів, також не доречна. Пояснимо це на прикладі функції , яка представляється рядом , , у якому абсолютна величина чисел Бернуллі . 6 Зрозуміло, що обчислення функції у такий спосіб складно. Тому обчислення цієї функції краще виконувати за формулою , у якій ряди для функцій і одно типові, і можна організувати один рекурсивний процес, з якого вибирати необхідні значення для по черзі для функцій і . Однак ситуація покращується, скористатися представленням функції ланцюговим дробом: Зауважимо, що від ланцюгового дробу легко перейти до ряду, але перехід від ряду до дробу це мистецтво. Особливості ланцюгових дробів: - їх простота, 7 - рекурсивне представлення і обчислення, - оптимальна кількість операцій і їх типізація. Так у наведеному дробу явно використовується дві операції: віднімання і ділення та одна неявна операція складання. Школа Лебєдєва С.А. використовувала ланцюгові дроби у 60 роках попереднього століття, а американці тільки тепер.
|