Рекурсивные методы программирования

Рекурсивное программировани е 11 класс профильный уровень

МОУ «Школа-лицей №1»

г. Алушта

Учитель: Литвинович Валентина Петровна

Рекурсивные подпрограммы- функции и процедуры в Паскале

• При написании программ с использованием подпрограмм-функций и процедур, допускается обращении подпрограммы-функции или процедуры к самой себе.

• Рекурсия  ‒ это такой способ организации вспомогательного алгоритма подпрограммы, при котором эта подпрограмма (процедура или функция) в ходе выполнения ее операторов обращается сама к себе.

Что такое подпрограмма ?

• - автономная часть программы, выполняющая определенный алгоритм и допускающая обращение к ней из различных частей общей программы.

• -Используются в случаях, когда в подпрограмме необходимо получить несколько результатов различных частей общей программы.

Рассмотрим ряд рекурентной последовательности

Вычисление 5!

• 5! = 5 * 4 * 3 * 2 * 1 =5 * 4!= 120
• 4! = 4 * 3 * 2 * 1 = 4* 3!= 24
• 3! = 3 * 2 * 1 = 3* 2!= 6 F3=F(3-1)/3
• 2! = 2 * 1 = 2* 1!= 2
• 1! = 1* 0!= 1
• 0! = 1
• Представляем n! как n*(n-1)!

1 Вход в рекурсию! обращение 1 Обращение 3 Обращение 2 Function FN (n: integer): real; Function FN (n: integer): real; Begin Begin If n=0 then FN:=1 If n=0 then FN:=1 else FN:=FN (2-1)/2 else FN:=FN(1-1)/1 end; end; Function FN (n: integer): real; Begin If n=0 then FN:=1 else FN:=FN (3-1)/3 end; возвращение " width="640"

ОПРЕДЕЛЯЕМ Fn = 1/3!

1, при n = 0

Fn(3)= Fn = (Fn – 1)/n, при n 1

Вход в рекурсию!

обращение 1

Обращение 3

Обращение 2

Function FN (n: integer): real;

Function FN (n: integer): real;

Begin

Begin

If n=0 then FN:=1

If n=0 then FN:=1

else FN:=FN (2-1)/2

else FN:=FN(1-1)/1

end;

end;

Function FN (n: integer): real;

Begin

If n=0 then FN:=1

else FN:=FN (3-1)/3

end;

возвращение

Программы вычисления Fn = 1/ n!

Пример1

Пример 2

Function FN (n: integer): real;

Function FN (n: integer): real;

Var i: integer; F: real;

Begin

If n=0 then FN:=1

Begin

F:=1

else FN:=FN (n-1)/n

end;

For i:=1 to n do F:=F/i;

FN:=F

end;

Обращение к самой себе

Функции Fn

Нерекурсивный вариант программы циклической структуры

ВНИМАНИЕ !

Рекурсивнный вариант программы

При выполнении оператора Fn:=(Fn – 1)/n , происходит цепочка рекурсивных обращений к оператору с последующим возвращением

Вход в рекурсию

• Fn(3 ) Fn(2 ) Fn(1) Fn(0) =1

Fn(1)=1

Fn(2)=1/2

Fn(3)=0.5/3

возврат

Результат –0.166..

ВАЖНО!

Специальный раздел памяти, в который при каждом обращении к функции помещается необходимая информация (адрес команды, адрес ячейки, где находятся промежуточные значения и т.д.) для реализации обратного процесса вычислений, называют СТЭКОМ.

Вычисление частично-рекурсивной функции может быть реализовано с помощью рекурсивной процедуры:

Пример:

Var X: real;

Procedure FN(n: integer; var F: real);

begin

if n=0 then F:=1

else begin FN(n-1,F); F:=F/n end

end.

begin

FN(5,X); Write(x)

end.

ПРОТЕСТИРОВАТЬ!

.

Объявление процедуры

Тело подпрограммы

Что выполняет программа?

Вывод: частично рекурсивную функцию можно запрограммировать на Паскале используя рекурсивную подпрограмму функцию или подпрограмму процедуру, такая программа имеет ветвящую структуру вместо циклической нерекурсивной. Рекурсивное программирование упрощает само решение программы, но для выполнение рекурсивных программ идет больше времени машинного времени и требует дополнительной памяти для заполнения стека ВАЖНО! В рекурсии должно быть граничное условие, при выходе на которое рекурсия прекращается!!!

РЕКУРСИЯ (Физминутка)

Самоподобие изображения

Известный математик в средневековье. Леонардо Пизанский (Фибоначчи )

Числа Фибонначчи

• . Каждое число равно сумме двух предыдущих чисел при условии, что первые два равны 1.
• (1, 1, 2, 3, 5, 8, 13, 21, …).

Домашнее задание: § 2.3.1; стр 136-142; № 1,2.

ЗОЛОТАЯ СПИРАЛЬ

Практическая работа

Написать программу вычисления суммы рекурентного ряда для n=4

Представить в виде S(n)

Программа вычисление суммы членов рекурентного ряда n!

Program Summa_1;

Var E, a: real;

N,i: integer;

begin

Write('N=');

Readln(N);

E:=0; i:=0; a:=1;

while i

begin

E:=E+a;

i:=i+1;

a:=a/i;

end;

Writeln('E', E)

end.

Program Summa4;

Var M: integer ;

Function SUM(K: integer ): real;

Function FN (n: integer ): real;

begin

if n=0 then FN:=1

else FN:=FN(n-1)/n

end;

begin

if K=0 then SUM:=1

else SUM:=SUM(K-1)+FN(K);

end;

begin

Write(' M ='); Readln(M);

Write('E=', SUM(M))

end.

Рекурсивная программа

Циклическая прогр-мма