Рекурсия

← →
Svin (2002-09-23 14:56) [0]

Здраствуйте уважаемые мастера помогите пожалуста в таком вопросе
есть задачка которую нужно зделать рекурсией я чегото немогу придумать как это осуществить
а без рекурсии я сдела но препод непринимает
вот задача:
Информация находится в текстовом файле и содержит положительные и отрицательные числа. Вывести
отрицательные числа в обратном порядке.
Заранее благодарен

← →
Внук (2002-09-23 15:19) [1]

1. Открыть файл и встать на первую позицию в нем.
2. Найти первое от текущей позиции отрицательное число, занести в локальную переменную.
3. Если найдено - перейти к пункту 2 (рекурсия) и затем напечатать найденное число
4. Если не найдено - выход (условие выхода из рекурсии)

← →
MBo (2002-09-23 15:23) [2]

Рекурсия здесь за уши притянута
примерно так

procedure BackNeg;
begin
if not eof then begin
прочитать строку
извлечь число
BackNeg;
если отрицательное, вывести
end;
end;

← →
Cu (2002-09-23 15:42) [3]

Блин.. Не соображается .. понедельник :(
Короче сортировку тебе надо наверно рекурсивной сделать
(что-то мне подсказывает)

← →
gek (2002-09-23 15:47) [4]

Да зачем сортировку делать?
Борис правильно написал, этого вполне достаточно, ведь сказано было сделать с рекурсией - сделал. А сортировку в ListBox можно сделать, что бы не сильно извращаться

← →
Внук (2002-09-23 15:47) [5]

Рекурсией "естественным образом" здесь достигается обратный порядок при печати :))

← →
Svin (2002-09-23 18:31) [6]

Народ спасибо ОГРОМНОЕ ВСЁ работает
но вот появился вопросик
вот исодный текст
procedure Tform1.getNum;
var
s:string;
Begin
if not eof(FILEDATA) then
Begin
ReadLn(FileDATA,s);
GetNum;
if StrToInt(s)<0 then listbox1.Items.Add(s);
End;
End;
Немогли бы вы обьяснить поподробней почему всё выводится именно
в обратном порядкеи как всё действует а то я несильно вьехал

← →
keymaster (2002-09-23 18:34) [7]

хм.... а чего тут непонятного?
оно по другому и не должно работать...

для понимания, возьми лист бумаги, карандаш
и по старинке блок-схемку нарисуй :)

← →
Svin (2002-09-23 18:36) [8]

здесь переменная s читается один раз и поэтому неочень понятно
почему всё происходит с конца здесь что когда процедура вызывается при каждом разе создаётся копия s или как

← →
MBo (2002-09-23 18:41) [9]

да, при каждом рекурсивном вызове в стеке создается своя копия.
Кстати, можно и так

Begin
if eof(FILEDATA) then Exit
ReadLn(FileDATA,s);
GetNum;
if StrToInt(s)<0 then listbox1.Items.Add(s);
End;

← →
Svin (2002-09-24 08:19) [10]

Спасибо MBo но почему if StrToInt(s)<0 then listbox1.Items.Add(s); Начинает с последней копии
И откуда оно знает что всё начинается с последнего там же копии некак ненумеруются

← →
MBo (2002-09-24 08:41) [11]

Тебе знакомо понятие стека (последним вошел, первым вышел)?
Аналогией может служит стопка тарелок.
При кажлом вызове процедуры в стек записываются (создаются) ее локальные переменные (и еще кое-что, в данном случае неважно).
Подпрограмма работает с ними через указатель на вершину стека (SP,BP) и смещение относительно него.
Утрированный пример (не различая sp и bp)
В процедуре используются 2 Integer переменные.
Первая находится по адресу BP-4, вторая по адресу BP.
Если вызвать из нее себя же, в стеке появятся два новых числа, в новой реинкарнации процедуры адрес BP сместится, но для нее опять же первая будет по адресу BP-4, вторая по адресу BP (заметь, что BP в ней отличается от первого). Когда процедура завершается, со стека снимаются ее лок. переменные, указатель BP смещается в то положение, в каком он был до ее вызова. Мы возвратились в первую копию процедуры, ее локальные переменные снова доступны, при выходе из нее они снимаются, указатель стека сдвигается.

В твоей задаче в конце цепочки рекурсивных процедур стек выглядит так
S(1)
S(2)
S(3)
...
S(n)

где S(i) - строка для i-1 итерации процедуры.
При возврате из последнего вызова СНАЧАЛА выводится S(N) (последняя локальная перменная в стеке) и Т.Д.

← →
Svin (2002-09-24 09:54) [12]

Круто !!
Теперь всё понятно спасибо

Рекурсия Найти похожие ветки