IPB
ЛогинПароль:

> Правила раздела!

1. Заголовок или название темы должно быть информативным !
2. Все тексты фрагментов программ должны помещаться в теги [code] ... [/code] или [code=pas] ... [/code].
3. Прежде чем задавать вопрос, см. "FAQ" и используйте ПОИСК !
4. НЕ используйте форум для личного общения!
5. Самое главное - это раздел теоретический, т.е. никаких задач и программ (за исключением небольших фрагментов) - для этого есть отдельный раздел!

 
 Ответить  Открыть новую тему 
> Рекурсия? Что же это такое?, Помогите
сообщение
Сообщение #1


Бывалый
***

Группа: Пользователи
Сообщений: 195
Пол: Мужской
Реальное имя: Сергей

Репутация: -  2  +


Ну так вот на многих сайтах с задачами (не только acmp.ru) я находил такое определение, как рекурсия. Не могли бы Вы рассказать всё (ну что Вы знаете), что нужно юному программисту, для знания данной темы.


--------------------
♣♣♣
"Себя великим не считай, гордясь величьем предков,
Величья не добудешь ты и золота ценою!
Хоть светит на небе луна, но отраженным светом -
Чужою славой не живи, не будь второй луною!!!"
♣♣♣
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Гуру
*****

Группа: Пользователи
Сообщений: 1 220
Пол: Мужской

Репутация: -  16  +


Берется любой хороший учебник по Паскалю и читается.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


Бывалый
***

Группа: Пользователи
Сообщений: 195
Пол: Мужской
Реальное имя: Сергей

Репутация: -  2  +


А в учебнике "В.Б. Попова Turbo Pascal для школьников", там вроде нет(((


--------------------
♣♣♣
"Себя великим не считай, гордясь величьем предков,
Величья не добудешь ты и золота ценою!
Хоть светит на небе луна, но отраженным светом -
Чужою славой не живи, не будь второй луною!!!"
♣♣♣
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Гость






В принципе, берется любой учебник по любому языку, и читается. Рекурсия - это не то, что доступно только в Паскале.

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

Цитата
А в учебнике "В.Б. Попова Turbo Pascal для школьников", там вроде нет(((
Значит, бери другой учебник.
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


Гуру
*****

Группа: Пользователи
Сообщений: 1 220
Пол: Мужской

Репутация: -  16  +


В Фаронове есть.
http://pascal-books.narod.ru/books/faronov.zip
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Бывалый
***

Группа: Пользователи
Сообщений: 195
Пол: Мужской
Реальное имя: Сергей

Репутация: -  2  +


Ну я так понял что в основном рекурсия выполняетя с помощью подпрограмм (процедур и функций)?


--------------------
♣♣♣
"Себя великим не считай, гордясь величьем предков,
Величья не добудешь ты и золота ценою!
Хоть светит на небе луна, но отраженным светом -
Чужою славой не живи, не будь второй луною!!!"
♣♣♣
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


Гуру
*****

Группа: Пользователи
Сообщений: 1 220
Пол: Мужской

Репутация: -  16  +


Ну да. Найдите какие-нибудь классичсекие примеры. Вычисление факториала, например.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Цитата(Сергей Меркурьев @ 14.05.2009 15:26) *
рекурсия выполняетя с помощью подпрограмм (процедур и функций)?
Проще говоря, рекурсия - это когда подпрограмма (или функция) вызывается в ней самой. Ре-курс - буквально: повторный заход (как ре-монт - повторный монтаж).

Факторил - замечательный пример.
n! = 1*2*3*4..*(n-1)*n
- это его прямое определение.

А вот рекурсивное определение:
n! = (n-1)!*n
и
0!=1

Состаявляем функцию для его вычисления в соответствии с прямым определением:
function Fuctorial(n: integer): LongInt;
var
i: integer;
f: LongInt;
begin
f:=1;
for i:=1 to n do f:=f*i;
Factorial:=f
end;


А вот функция, составленная рекуррентно:
function Fuctorial(n: integer): LongInt;
begin
if n=0 then Factorial:=1 else Factorial:=n*Factorial(n-1)
end;


Вторая выглядит намного проще, согласись. Что происходит? Кога в нее заходишь, например, со значением n=3, она пытается умножить это значение на факториал двойки, который еще не знает. Она вызфывает функцию для вычисления этого факториала двойки, и уже та пытается 2 умножить на факториал 1. Снова то же самое: та вызывает факториал 0, чтобы вычислить факториал 1. И вот когда вызван факториал 0 - тогда происходит нечто другое: функция выходит со значением 1 в соответствии с первой частью условного оператора в ней.

А дальше разворачивается обратная цепочка. Вызов факториала 0 возвращает 1, домножает его на 1 и возвращает эту единицу экземпляру функции, который вызвал факториал 2. Та получает ее, домножает на 2 и возвращает. Следующий экземпляр функции получает эту двойку, домножает ее на 3 и снова возвращает полученную шестерку - теперь уже тебе.

Технически, происходит следующее. При каждом вызове функции всякий раз создается отдельная копия ее переменных, включая параметры. Именно с ними производятся действия, поэтому копии (экземпляры) функции они не мешают друг другу. При этом код (набор инструкций) только один.

Пример с факториалом - самый простой. Поиск по Форуму может дать тебе много интересных примеров)). Если будут трудности с поиском - пиши, я найду ченть.


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #9


Гость






Олег даже тему открывал в свое время для интересных рекурсивных решений: Рекурсия

Но что-то ее забросили. Андрей, если наткнешься на что-нибудь интересное, сохрани ссылку, потом добавим в ту тему, чтоб легче искать было... smile.gif
 К началу страницы 
+ Ответить 
сообщение
Сообщение #10


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Цитата(volvo @ 14.05.2009 17:07) *
Но что-то ее забросили. Андрей, если наткнешься на что-нибудь интересное, сохрани ссылку, потом добавим в ту тему, чтоб легче искать было... smile.gif
Угу, я даже и не знал про нее((, до меня было. Конечно, можно даже специально поискать. Было много, заслуживающего внимания..

Добавлю по теме: несмотря на ее внешнюю привлекательность, использовать рекурсию нужно осторожно. Дело в том, что она очень сильно расходует ресурсы: как память, так и процессор. Все экземпляры живут в стеке. В 32-битных компиляторах его размер, как правило, достаточно большой, но в ТР/ВР это всего 64К. Можешь запустить многократный подсчет факториала и убедиться в этом сам. Там, где в прямой функции нужно всего лишь одно умножение (плюс один шаг цикла), то в рекурсивной вызов процедуры со всеми вытекающими..

Кстати не пытайся посчитать, скажем, факториал 30.. Это очень быстро растущая функция. Она вылетит по значению раньше, чем по ресурсам)).


Добавлено через 3 мин.
А чтобы наблюдать вылет по переполнению стека, можешь попытаться (кстати, для практики) реализовать функцию "вопросиал"))

n? = 0 + 1 + 2 + 3 + 4 + .. + (n-1) + n

Может, потребуется использовать LongInt


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #11


Бывалый
***

Группа: Пользователи
Сообщений: 195
Пол: Мужской
Реальное имя: Сергей

Репутация: -  2  +


В общем то про факториал я знаю, и, что значение 30!, значение которого черезчур велико (265252859812191058636308480000000)... А вот про информацию Вам спасибо, к сожалению я ещё не приступил к изучению функций и процедур).

А вот не могли бы Вы сказать мне каким образом можно найти последнюю ненулевую цифры любого факториала??? Я попытался решить такую задачку сохраняя последние 6 цифр его, и последовательно удаляя все нули) Но вот только после значений Х>99 там уже начинаются проблемы)))

program metro;
var N,F,R:longint;
begin
assign (input,'input.txt');
reset (input);
assign (output,'output.txt');
rewrite (output);
Read (N);
F:=1;
R:=1;
While R<=N do
Begin
F:=F*R;
R:=R+1;
If F mod 10=0 then Begin
F:=F div 10;
If F mod 10=0 then F:=F div 10
End;
If F>999999 then F:=F mod 10;
End;
If F mod 10<>0 then Write (F mod 10)
else Write (F mod 10);
End.



--------------------
♣♣♣
"Себя великим не считай, гордясь величьем предков,
Величья не добудешь ты и золота ценою!
Хоть светит на небе луна, но отраженным светом -
Чужою славой не живи, не будь второй луною!!!"
♣♣♣
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #12


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Цитата(Сергей Меркурьев @ 14.05.2009 20:35) *
А вот не могли бы Вы сказать мне каким образом можно найти последнюю ненулевую цифры любого факториала???
Стоп! Это уже не теретический вопрос, как и не про рекурсию.
С предметом темы разобрался, вопросов больше нет?


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #13


Бывалый
***

Группа: Пользователи
Сообщений: 195
Пол: Мужской
Реальное имя: Сергей

Репутация: -  2  +


В принципе если Вас не затруднит рассказать мне про подпрограммы (хотя я это и сам почитаю), тогда всё)


--------------------
♣♣♣
"Себя великим не считай, гордясь величьем предков,
Величья не добудешь ты и золота ценою!
Хоть светит на небе луна, но отраженным светом -
Чужою славой не живи, не будь второй луною!!!"
♣♣♣
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #14


Уникум
*******

Группа: Пользователи
Сообщений: 6 823
Пол: Мужской
Реальное имя: Лопáрь (Андрей)

Репутация: -  159  +


Цитата(Сергей Меркурьев @ 14.05.2009 21:01) *
В принципе если Вас не затруднит рассказать мне про подпрограммы (хотя я это и сам почитаю), тогда всё)
Нет проблем - спрашивай. Ты только пойми, что Форум требует организации. Это важно для тех, кто потом использует поиск. Хочешь про подпрограммы - открой тему про подпрограммы. Нельзя все валить в одну кучу, даже если и есть какая-то связь.
Про эту тему, про рекурсию - все?


--------------------
я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #15


Бывалый
***

Группа: Пользователи
Сообщений: 195
Пол: Мужской
Реальное имя: Сергей

Репутация: -  2  +


В принципе про рекурсия да!


--------------------
♣♣♣
"Себя великим не считай, гордясь величьем предков,
Величья не добудешь ты и золота ценою!
Хоть светит на небе луна, но отраженным светом -
Чужою славой не живи, не будь второй луною!!!"
♣♣♣
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #16


Гость






Ну, еще не мешало бы сказать про особый тип рекурсии: хвостовую (правую) рекурсию, когда собственно рекурсивный вызов производится после всех остальных необходимых вычислений (у Lapp-а в посте №8 приведена именно такая реализация вычисления факториала). То есть, вот это:
function Factorial(n: integer): LongInt;
begin
if n=0 then Factorial:=1 else Factorial:=Factorial(n-1)*n
end;
уже не хвостовая рекурсия, потому что рекурсивный вызов - не последний, после него есть еще вычисления... А разница - в том, что хвостовую рекурсию многие оптимизирующие компиляторы сводят к итерации, а значит, выполняться она будет быстрее и без доп. затрат памяти. Насчет Паскаль-компиляторов не знаю, чтоб кто-нибудь умел такое, но вот С++ компиляторы (в частности VC7+ от Microsoft, GCC из "GNU"-тых и ICC от Intel) прекрасно с данной задачей справляются.

Кстати, создатели FPC утверждают, что версия 2.2 тоже уже умеет оптимизировать хвостовую рекурсию, но надо будет проверить...

P.S. Я сам везде, где можно стараюсь использовать именно этот способ. Возможно, и не поможет, но не помешает - точно. А если когда-нибудь используемый компилятор научится оптимизировать такое - то не надо будет переписывать код smile.gif
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 29.03.2024 5:18
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name