Главная | Обратная связь | Поможем написать вашу работу!
МегаЛекции

Смоделируем выполнение рекурсивной программы на Бейсике.




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

Обращение к подпрограмме пусть происходит оператором 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.

Имитация исполнения рекурсивных программ с использованием таблиц и графов.

Поделиться:





Воспользуйтесь поиском по сайту:



©2015 - 2024 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...