Embedded Files
Теория.
Рекурсия — вызов функции из неё же самой, непосредственно (простая рекурсия) или через другие функции (сложная или косвенная рекурсия), например, функция A вызывает функцию B, а функция B — функцию A.
Программа разрабатывается сведением исходной задачи к более простым. Среди этих задач может оказаться и первоначальная, но в упрощенной форме.
Например, для вычисления F(N) может понадобиться вычислить F(N−1). Иными словами, частью алгоритма вычисления функции будет вычисление этой же функции.
Итак, функция является рекурсивной, если она обращается сама к себе прямо или косвенно (через другие функции). Заметим, что при косвенном обращении все функции в цепочке – рекурсивные.
Для решения этого задания необходимо построить дерево, если в рекурсии два действия, и цепочку, если одно.
Пример задания.
procedure F(n: integer);
begin
writeln(n);
if n>1 then
begin
F(n-1);
F(n-2);
end;
end;
Определите сумму цифр, выведенных на экран при выполнении процедуры F(5).
При построении дерева, для упрощения заменим F(5) просто на 5, F(4) на 4, и т.д.
Также заметьте, что число будет напечатано на экране даже, если не выполнится последующее условие (так как сначала идет вывод, а затем передача в рекурсию). Рекурсия же закончится в тот момент, когда будет передано значение 1, или 0.
Теперь просто сосчитаем суммы всех чисел:
5+4+3+3+2+2+1+2+1+1+0+1+0+1+0=26
Ответ 26.
Примечание. Так как значения в древе повторяются нет необходимости строить дерево целиком, достаточно правильно подсчитать количество вариантов в ветках.
Пример задания.
Procedure F(n: integer);
begin
if n mod 2 = 0 then
writeln(‘*’)
else
writeln(‘**’);
if n>0 then
F(n-1);
end;
Сколько символов "звёздочка" будет выведено на экран при вызове процедуры F(6)?
Построим цепочку, которая покажет последовательность вызова функций:
F(6)->F(5)->F(4)->F(3)->F(2)->F(1)->F(0)
Причем, если значение, передаваемое в F четное ( n mod 2 = 0 ), то будет напечатана 1 звездочка, иначе 2, так как четных 4 числа, а нечетных 3 получаем:
4*1+3*2=10
Ответ 10.
Пример задания.
Ниже на языках программирования Python и Pascal записана рекурсивная функция F.
Python:
def F(n):
if n > 2:
return F(n-2) + F(n//2)
else:
return n
Pascal:
function F (n: integer): integer;
begin
if n>2 then
F:=F(n-2)+ F (n div 2)
else
F:=n
end;
Чему будет равно значение, вычисленное при выполнении вызова F(9)?
Найдем значение F(9):
F(9):= F(7)+ F(4)
Необходимо теперь найти F(7) и F(4):
F(7):= F(5)+ F(3)
F(4):= F(2)+ F(2)
Находим остальные значения:
F(2):= 2
F(3):=F(1)+F(1)
F(1):=1, получаем F(3):=1+1=2
F(5):=F(3)+ F(2)=2+2=4
F(7):=4+2=6
В итоге:
F(9):=6+4=10
Ответ 10.
Google Sites
Report abuse