Чтобы посмотреть презентацию с картинками, оформлением и слайдами, скачайте ее файл и откройте в PowerPoint на своем компьютере.
Текстовое содержимое слайдов презентации:
Новиков Алексей КонстантиновичПреподаватель СПК МГППУПрограммирование на Delphi Занятие 6 Рекурсия Рекурсивный свод правил Найдите в словаре слово.Прочитайте статью, объясняющую значение этого слова.Если объяснение понятно, то есть статья не содержит слов, вызывающих затруднение, продолжите чтение с последнего прерванного места.Если в объяснении встречается незнакомое слово, то прекратите чтение, запомните место прекращения и выясните значение слова, придерживаясь правилам 1-4. Определение рекурсии Рекурсия – это такой способ организации вычислительного процесса, при котором процедура или функция в ходе выполнения составляющих ее операторов обращается сама к себе. При использовании рекурсии необходимо обращать особое внимание на выход из подпрограммы в нужный момент. Пример Рекурсивное определение суммы первых n натуральных чисел. Сумма первых n натуральных чисел равна сумме первых (n-1) натуральных чисел плюс n, а сумма первого числа равна 1. Или Sn=S n-1+n; S1=1. Рекурсия полезна, прежде всего, в случаях, когда основную задачу можно разделить на подзадачи, имеющие ту же структуру, что и первоначальная задача. Подпрограммы, реализующие рекурсию, называются рекурсивными. Для понимания сути рекурсии лучше трактовать рекурсивный вызов как вызов другой подпрограммы. Интерация Интерация – повторяемое выполнение некоторых действий до тех пор, пока не будет удовлетворяться некоторое условие. Большинство алгоритмов можно реализовать двумя способами: интерацией и рекурсией. Особенности рекурсии: Использование рекурсивной формы организации алгоритма обычно выглядит изящнее интерационной и дает более компактный текст программы;Недостатки рекурсии:Если глубина рекурсии очень велика, то программа будет требовать во время выполнения много памяти – это может привести к переполнению стека; Рекурсивные алгоритмы, как правило, выполняются более медленно;При рекурсивном программировании велика вероятность ошибок, способных вынудить программиста к перезагрузке компьютера. Пример Рассмотрим листинг программы, которая вычисляет сумму первых n членов гармонического ряда 1+1/2+1/3+... с использованием процедуры sumset, предусматривающей традиционное накопление суммы в цикле for и процедуры recursion. Var n: integer; S: real; Procedure sumset (n: integer; var sum: real); var i: integer; Begin Sum:=0; For i:=1 to n do sum:=sum+1/i; End; Procedure recursion (n: integer; var sum: real); Begin If n=1 then sum:=1+sum Else begin Sum:=sum+1/n; Recursion (n-1,sum); End; End; BeginWriteln (‘Введите количество суммированных членов ряда’); Readln (n);Sumset (n, s);Writeln (‘Сумма членов ряда равна (цикл)’,s);S:=0; recursion (n, s);Writeln (‘Сумма членов ряда равна (рекурсия)’,s); end. Пример нахождения чисел ряда Фибоначчи с обычной процедурой. Procedure fibo (n: integer); var fn, fn1, fn2, k: integer; begin fn1:=1; fn:=0; for k:=1 to n do begin fn2:=fn1; fn1:=fn; fn:=fn1+fn2; writeln (fn); end; end; {основная программа}var n: integer;beginwrite (‘Введите число членов рядов Фибоначчи ’);readln(n),fibo(n);end. F-1=1, F0=0.Если превратить фиктивные члены в параметры, то можно получить процедуру, печатающую n членов ряда, идущих за двумя данными членами. Модифицируем процедуру с fibo, превратив переменные fn1 и fn в параметры, не приписывая им начальных значений. {рекурсивная процедура вычисления и печати чисел Фибоначчи}Procedure fibonachi (n, fn1, fn: integer);begin if n>o then begin writeln (fn1+fn);fibonachi (n-1, fn, fn1+fn);end;end; {основная программа}var n, a, b: integer;begin write (Введите число членов ряда Фибоначчи:);readln (n);write (‘…следующих за двумя данными членами:’)readln (a, b); fibonachi (n, a, b);end. Если пользователь захочет вывести на экран n=10 первых членов ряда Фибоначчи, то он должен указать в качестве а и b два фиктивных члена - 1 и 0 соответственно. Если нужно вывести 10 членов ряда, начиная с 6-го, необходимо вывести для n, a, b числа 10, 3 и 5 соответственно.
Приложенные файлы
