 |
Смоделируем выполнение рекурсивной программы на Бейсике.
|
|
|
|
Подпрограмма в Бейсике есть часть общей программы. Пронумеруем строки программы и рассмотрим, как устройство управления выполнит рекурсивную программу.
Обращение к подпрограмме пусть происходит оператором GOSUB (номер строки). При этом в стеке возврата запоминается адрес начала следующего оператора. Выход из подпрограммы происходит по оператору RETURN, причем в качестве адреса перехода берется последнее значение из стека возврата. Покажем, как этот механизм используется для организации рекурсивной подпрограммы.
Зачем нужна «самодельная» рекурсия?
Самостоятельная реализация рекурсивного алгоритма позволяет глубже разобраться и в механизме исполнения рекурсивных программ и глубже понять использование обычной конструкции — подпрограммы.
Задача: Описать алгоритм печати на экране чисел от 1 до 5, а потом в обратном порядке от 5 до 1.
Рассмотрим следующий пример:
10 REM======= ПPИMEP РЕКУРСИИ =========
15 REM………….основная программа………..………
20 К =1
30 GOSUB 100 ’40 в стек адресов возврата…………..
40 END…………’.конец основной программы……………
100 REM……………………………………………………….
110 REM РЕКУРСИВНАЯ ПОДПРОГРАММА
120 REM-------- ‘спуск……………………………………
130 PRINT К
140 IF K = 5 GOTO 170
150К = К+1
160 GOSUB 100 …………’170 в стек адресов.возврата....
170 REM………’подъём……………………………………
175 К = К-1
180 PRINT К
190 RETURN..’ возврат на команду, адрес которой в стеке адресов
200 REM ‘ КОНЕЦ ПОДПРОГРАММЫ
При первом обращении к рекурсивной подпрограмме из строки 30 в стек возврата будет записан адрес строки 40, при втором обращении — из строки 160 — адрес следующей строки (170) и т. д. Проследим за стеком возврата.
Стек возврата
1 40
2 170 40
3 170 170 40
4 170 170 170 40
|
|
|
5 170 170 170 170 40 6 170 170 170 40
7 170 170 40
8 170 40
9 40
Адреса для возврата по оператору RETURN берутся из стека в обратном порядке (в таблице они выделены рамками). В последнюю очередь будет выполнен возврат к строке 40 и останов по оператору END.
К – 1.2.3.4.5,4,3,2,1
Структура примера характерна для записи рекурсивных программ на Бейсике. Строки 10—40 —это основная программа, в которой задаются начальные значения параметров, производится первое обращение к рекурсивной подпрограмме и останов после ее выполнения. Строки 100— 200—это рекурсивная подпрограмма. Вывод параметра К позволяет проследить за переходами с одного уровня рекурсии на другой: он увеличивается на единицу перед каждым обращением к подпрограмме и уменьшается на единицу перед выходом из нее.
Главной проблемой при организации рекурсии является сохранение результатов работы рекурсивной подпрограммы при последующих самообращениях. В языках, допускающих рекурсию, при спуске, то есть при обращении к подпрограмме 1 – ый раз, 2 – ой раз и т. д, создаются новые экземпляры используемых переменных. Они «закрывают своим телом» прежние значения. При подъёме становятся доступными те переменные, на которые указывает указатель стека.
Для реализации этого механизма на Бейсике приходится хранить значения переменных на всех уровнях рекурсии, т. е. каждую простую переменную нужно заменить таблицей. Эту идею поясняет рис.1. В данный момент программе доступны только Х(К), Y(K) Z(K). При сдвиге указателя К вверх «откроются» Х(К—1), Y(K—1), Z(K—1), при сдвиге вниз — Х(К+1), Y(K+1), Z(K +1).
Рекурсия на TURBO PASCAL
Факториал
program prfact;
var n:integer;l:longintl;
procedure fact (m:integer; var f:longintl);
begin
if m=1 then
f:=1
else begin
fact(m-1,f);
f:=f*m
end;
end;
begin
write(‘Введите N’);
readln(N);
fact(n,l);
writeln(l:6:3)
end.
program factrec;
var n:integer;l:longint;
function fact (m:integer):longint;
begin
if m=1 then fact:=1 else fact=fact(m-1)*m
end;
begin
writeln(‘Введите N’);
readln(N);
l:=fact(n);
writeln(l:6:3)
end.
|
|
|
Рекурсия на QBasic
DECLARE FUNCTION FACT! (k AS INTEGER)
REM ФАКТОРИАЛ
DIM n AS INTEGER
INPUT “ВВЕДИТЕ N”;n
PRINT “n=”;n
S=FACT((n)) ‘можно без скобок – результат тот же
PRINT “n=”,n
PRINT “ФАКТОРИАЛ N=”;S
END
FUNCTION FACT (k AS INTEGER) ‘STATIC можно без STATIC
PRINT “k=”;k
IF k=1 THEN
FACT=1
ELSE
FACT=FACT(k-1)*k
END IF
END FUNCTION
Рекурсияна LOGO
| Задача 1. это кв:а по если:а < -200 [стоп] повтори 4 [плавно:а 1 пр 90] пр 1 кв:а - 5 конец | Задача 2. это спираль:а если:а < 2 [стоп] вп:а пр 90 спираль:а - 5 конец |
Программа на языке Turbo Pascal игры Ханойская башня
(с использованием рекурсии)
Знакомиться с рекурсией лучше на примерах, где механизм исполнения рекурсивных алгоритмов легко объяснить (факториал, числа Фибоначчи, …), а необходимость использования рекурсии при описании алгоритмов решения задач лучше продемонстрировать на реализации рекурсивных алгоритмов таких практических задач как, например, Ханойская башня.
Задача. Несколько дисков различных размеров нанизаны на один из нескольких стержней, образуя пирамидку (башню), чем выше находится диск, тем меньше его диаметр. Требуется переместить эту пирамидку на другой стержень, соблюдая следующие правила: за один раз можно перекладывать только один диск; нельзя класть диск на меньший по диаметру диск; можно пользоваться только одним резервным стержнем
Program Hanoi; {Ханойская башня, программа с использованием рекурсии}
Uses crt;
Var a,b,c,n:integer;
Procedure Hanoi(i:integer;s,d,e:integer);
Begin
If i=1 then
Writeln(' ',s,'-',d)
else
begin
Hanoi(i-1,s,e,d); Hanoi(1,s,d,e); Hanoi(i-1,e,d,s);
end;
End;
Begin
Write ('введите кол-во дисков n='); Readln(n);
Writeln ('укажите начальный, конечный и промежуточный стержни:');
Readln(a); Readln(b); Readln(c); Hanoi(n,a,b,c);
End.
Имитация исполнения рекурсивных программ с использованием таблиц и графов.
|
|
|
