ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Что такое рекурсия, есть ли доходчивая инфа?
25 сообщений из 81, страница 2 из 4
  2  все
Что такое рекурсия, есть ли доходчивая инфа?
    #36532256
ShSerge
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ShSerge
Участник
А слабо написать программу, которая печатает свой текст?
...
Рейтинг: 0 / 0
20.03.2010, 11:00:07
| Ответить | Цитировать | Написать  
Что такое рекурсия, есть ли доходчивая инфа?
    #36532257
Фотография Рремешок
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Рремешок
Участник
ShSergeА слабо написать программу, которая печатает свой текст?и запускает этот текст на выполнение...
...
Рейтинг: 0 / 0
20.03.2010, 11:01:43
| Ответить | Цитировать | Написать  
Что такое рекурсия, есть ли доходчивая инфа?
    #36532437
RT183.5
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
RT183.5
Участник
ShSergeА слабо написать программу, которая печатает свой текст?
Вот чего не могу написать так это квайна
На контестере есть и супер-квайн http://www.spoj.pl/problems/SELF/
...
Рейтинг: 0 / 0
20.03.2010, 14:56:08
| Ответить | Цитировать | Написать  
Что такое рекурсия, есть ли доходчивая инфа?
    #36532583
Фотография SQL_Lamer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SQL_Lamer
Участник
Теперича вся сила в ООП-ях...

Код: plaintext
1.
2.
3.
4.
class OOPRecursion : IDisposable
    {
        public void Dispose() { using (OOPRecursion dr = new OOPRecursion()) { } }
    }
...
Рейтинг: 0 / 0
20.03.2010, 18:12:35
| Ответить | Цитировать | Написать  
Что такое рекурсия, есть ли доходчивая инфа?
    #36533921
Vowk
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Vowk
Участник
ShSergeА слабо написать программу, которая печатает свой текст?
Я когда-то выполнил это задание на Фортране (когда не было персональных ЭВМ). Программа занимала около 30 строк. Потом потерял решение. Потом снова сделал. Потом снова потерял.
...
Рейтинг: 0 / 0
22.03.2010, 10:26:58
| Ответить | Цитировать | Написать  
Что такое рекурсия, есть ли доходчивая инфа?
    #36533949
Vowk
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Vowk
Участник
А вообще понятие рекурсии идет из математики - рекуррентные соотношения. Числа Фибоначчи например - задаются через самих себя и начальное условие F(1) =1, F(2) = 2.
Без математического понимания рекурсии по-настоящему в программированнии рекурсивные программы не понять, я так считаю.
Но больше всего на меня впечатление производит функция Аккермана:
...
Рейтинг: 0 / 0
22.03.2010, 10:37:17
| Ответить | Цитировать | Написать  
Что такое рекурсия, есть ли доходчивая инфа?
    #36533950
ShSerge
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ShSerge
Участник
Vowk...Потом потерял решение. Потом снова сделал. Потом снова потерял.
Это рекурсия или итерация?
...
Рейтинг: 0 / 0
22.03.2010, 10:37:23
| Ответить | Цитировать | Написать  
Что такое рекурсия, есть ли доходчивая инфа?
    #36533964
Vowk
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Vowk
Участник
ShSerge,
итерация вместе с рекурсией :)
...
Рейтинг: 0 / 0
22.03.2010, 10:40:38
| Ответить | Цитировать | Написать  
Что такое рекурсия, есть ли доходчивая инфа?
    #36533987
ALKIR
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ALKIR
Участник
надо же как сложно объяснить, казалось бы простую вещь

уже две страницы нафлудили

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

в общем - не забивайте себе голову рекурсией раньше времени , когда понадобиться - сразу поймете что это такое!

//Я первый раз встретился с рекурсией, когда разбирался с алгоритмами закрашивания областей.
...
Рейтинг: 0 / 0
22.03.2010, 10:52:42
| Ответить | Цитировать | Написать  
Что такое рекурсия, есть ли доходчивая инфа?
    #36534084
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Какие Фибоначчи?!! Какие Аккерманы?!! Ребята! Это всё суть - учебные примеры! Это сферические кони в космосе!! Аккерман нужен только чтобы показать НЕ ПРИМИТИВНО рекурсивную ф-цию.

Реальный пример я уже привёл. Еще добавлю. Это обход дерева (Поиск элемента в XML документе используя только базовый API (для легких embedded систем), обход файловой системы, обход ВООБЩЕ ЛЮБОГО дерева). Это любые поиски в глубину и ширину . Работа с шаблоном класса compositor . Алгоритмы на графах . Синтаксический и семантический анализ текста . Поиск в интернете по ссылка м. +Графика (если автор будет заниматься), всякие там фрактальные сжатия .

Выбросьте из головы факториал и фибоначчи! Курите РЕАЛЬНЫЕ проблемы!
...
Рейтинг: 0 / 0
22.03.2010, 11:30:42
| Ответить | Цитировать | Написать  
Что такое рекурсия, есть ли доходчивая инфа?
    #36534152
Фотография S.G.
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
S.G.
Участник
VowkНо больше всего на меня впечатление производит функция Аккермана:Даа, это впечатляюще. Хорошая иллюстрация суждения: "сначала прикиньте, что должны получить, а потом давайте это компьютеру" :) А то я был знаком с программером, который делал цикл от 1 до 100! (факториал) (и пытался этот факториал держать в integer-е) и потом думал, а почему компьютер "виснет" :)

mayton
Выбросьте из головы факториал и фибоначчи! Курите РЕАЛЬНЫЕ проблемы!Надо же с чего-то начать, с более простого. :)
...
Рейтинг: 0 / 0
22.03.2010, 11:59:29
| Ответить | Цитировать | Написать  
Что такое рекурсия, есть ли доходчивая инфа?
    #36534157
Фотография S.G.
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
S.G.
Участник
мда, "Ханойские башни" вроде еще никто не вспомнил :)
...
Рейтинг: 0 / 0
22.03.2010, 12:02:07
| Ответить | Цитировать | Написать  
Что такое рекурсия, есть ли доходчивая инфа?
    #36534334
Фотография Denis.
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Denis.
Участник
S.G.мда, "Ханойские башни" вроде еще никто не вспомнил :)
Слишком просто они итерационно пишутся)
...
Рейтинг: 0 / 0
22.03.2010, 13:00:05
| Ответить | Цитировать | Написать  
Что такое рекурсия, есть ли доходчивая инфа?
    #36534353
Фотография ZyK_BotaN
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ZyK_BotaN
Участник
Denis.

-это косвенная рекурсия
...
Рейтинг: 0 / 0
22.03.2010, 13:06:58
| Ответить | Цитировать | Написать  
Что такое рекурсия, есть ли доходчивая инфа?
    #36536107
Bananas
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Bananas
Участник
Из всех примеров рекурсии чаще всего идет поиск в массиве. Получается, что рекурсия используется для обработки какого-либо ограниченного набора информации. Не могу вписать только примеры с зеркалами и стишком из вики; приведенными здесь рисунками.
Потом нашел определение, что если одна подзадача представляет собой уменьшенную версию исходной задачи, последнюю можно решить с помощью рекурсии. Т.е. одна итерация -- это подзадача?
...
Рейтинг: 0 / 0
23.03.2010, 09:47:35
| Ответить | Цитировать | Написать  
Что такое рекурсия, есть ли доходчивая инфа?
    #36536893
Фотография Denis.
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Denis.
Участник
Грубо, но чтоб понять: когда метод вызывает сам себя. Наиболее типичное использование - древовидные структуры. например надо написать название всех нодов в дереве. Возьмем некий нод - не корень и не лист, увидим что у него тоже ноды, и он является чьим то дочерним нодом, и у его дочерних нодов есть такие же ноды итд. В итоге удобно написать метод который будет делать примерно следущее:

МойМетод(нод)
{
написать_название_нода(нод);
foreach(var childNode in нод.Children)
МойМетод(childNode );
}
...
Рейтинг: 0 / 0
23.03.2010, 13:46:15
| Ответить | Цитировать | Написать  
Что такое рекурсия, есть ли доходчивая инфа?
    #36537726
Bananas
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Bananas
Участник
Denis.,
Ладно, давай по примеру с обходом дерева. Информация как бы структурирована: есть связанные узлы, у каждого узла есть листья. Получается однотипная задача: взять узел, просмотреть его листья; затем взять следующий узел и т.д. И есть не структурированная инфа -- простая последовательность, массив. Условие применения рекурсии не зависит от того, структурирована инфа или нет?
...
Рейтинг: 0 / 0
23.03.2010, 17:12:06
| Ответить | Цитировать | Написать  
Что такое рекурсия, есть ли доходчивая инфа?
    #36537932
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
BananasЛадно, давай по примеру с обходом дерева. Информация как бы структурирована: есть связанные узлы, у каждого узла есть листья. Получается однотипная задача: взять узел, просмотреть его листья; затем взять следующий узел и т.д. И есть не структурированная инфа -- простая последовательность, массив. Условие применения рекурсии не зависит от того, структурирована инфа или нет?
Термин структурированность имеет настолько много применений в том-же It (ЯП, структуры данных) что я-бы не рискнул вообще спорить о его смысле. Мы скатимся в глухую софистику и демагогию!

По поводу рекурсий . Тебе на первый взгляд может показаться что дерево обойти очень легко. Да! Легко когда ты имеешь интерфейс Итератор Дерева (который тоже будет рекурсивен внутри себя). Если ты его не имеешь то для движения по дереву и захода в узлы нужна стековая память (или списковая) для хранения доп. структур данных, которую НЕЛЬЗЯ реализовать КОНЕЧНЫМ АВТОМАТОМ. Здесь и пригодится стек.

По поводу применения рекурсии . Её можно применить практически ВЕЗДЕ! В языке LISP подсчёт ДЛИНЫ СПИСКА производит рекурсия. Но из этого вовсе НЕ СЛЕДУЕТ что надо так делать подсчёт везде. Просто среда LISP оптимизирована для легких функций car, cdr (или head, tail). И попытка применить рекурсию для суммы чисел a и b в императивном языке вызовет дикий оверхед по формированию параметров, callback-ам и прочим достаточно МАТЕРИАЛЬНЫМ вещам. Т.е. рекурсию надо применять ТОЛЬКО там где без рекурсии НЕВОЗМОЖНО обойтись. И попытка выразить сложение чисел через рекурсию, или подсчёт длины списка - не более чем красивое математическое доказательство СВОЙСТВА. Уверяю тебя, на практике ни один программист не складывает числа через рекурсию с декрементом.
...
Рейтинг: 0 / 0
23.03.2010, 18:17:21
| Ответить | Цитировать | Написать  
Что такое рекурсия, есть ли доходчивая инфа?
    #36538191
Фотография Denis.
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Denis.
Участник
"...рекурсию надо применять ТОЛЬКО там где без рекурсии НЕВОЗМОЖНО обойтись..."
Ну это чересчур конечно.
...
Рейтинг: 0 / 0
23.03.2010, 21:07:35
| Ответить | Цитировать | Написать  
Что такое рекурсия, есть ли доходчивая инфа?
    #36539176
Bananas
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Bananas
Участник
maytonУверяю тебя, на практике ни один программист не складывает числа через рекурсию с декрементом.
Но инструмент все равно полезный и кругозор расширяет.
Получается, рекурсией можно обработать любую информацию, главное определить повторяющийся алгоритм или типа того -- чтобы вынести в подзадачу. Тогда все примеры с вики вроде понятны, обход дерева тоже. Теперь такой вопрос ко всем: как из задачи "вычленить" этот повторяющийся элемент, который можно вынести в подзадачу? Можете привести пример ваших рассуждений, как сделать рекурсией появившуюся задачу? Интересно проследить за ходом мысли.
...
Рейтинг: 0 / 0
24.03.2010, 12:21:18
| Ответить | Цитировать | Написать  
Что такое рекурсия, есть ли доходчивая инфа?
    #36539322
zloy den
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
zloy den
Участник
Смотришь по итерациям, что меняется в каждой из них и пытаешься выловить общие и изменяющиеся части.

Очень в этом деле помогали правила нахождения уже упоминавшихся тут рекуррентных формул
...
Рейтинг: 0 / 0
24.03.2010, 13:00:27
| Ответить | Цитировать | Написать  
Что такое рекурсия, есть ли доходчивая инфа?
    #36541076
Фотография ZyK_BotaN
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ZyK_BotaN
Участник
zloy denСмотришь по итерациям, что меняется в каждой из них и пытаешься выловить общие и изменяющиеся части.

Очень в этом деле помогали правила нахождения уже упоминавшихся тут рекуррентных формул

зачем итерации заменять на рекурсию.
ИМХО, есть смысл использования рекурсии для рекурсивных задач. тех которые трудно
решаются или не решаются итеративным способом.
Примеры такой задачи(из СИКПа): сколькомя способами можно разменять определенную сумму, монетами
определенных номиналов.
...
Рейтинг: 0 / 0
24.03.2010, 23:36:24
| Ответить | Цитировать | Написать  
Что такое рекурсия, есть ли доходчивая инфа?
    #36541305
ALKIR
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ALKIR
Участник
ZyK_BotaN
ИМХО, есть смысл использования рекурсии для рекурсивных задач. тех которые трудно
решаются или не решаются итеративным способом .


:) любой алгоритм написанный через рекурсию может быть переписан в итерационной форме!!!

смысл использования рекурсии только в красоте кода (и переполнении стека)
...
Рейтинг: 0 / 0
25.03.2010, 09:01:05
| Ответить | Цитировать | Написать  
Что такое рекурсия, есть ли доходчивая инфа?
    #36541507
Vowk
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Vowk
Участник
Как справедливо тут говорилось, любой алгоритм можно записать как в рекурсивной, так и в итерационной форме. Рекурсивная форма получается меньше, но для понимания как бы сложнее.
На примере печати перестановок в Excel привожу два варианта решения задачи. Sub iter() печатает в первой колонке все перестановки итерационным способом, a Sub recurs() печатает все перестановки во второй колонке, и по количеству строк раза в два меньше. Для выполнения обоих примеров надо в Excel вызвать редактор Visual Basic и скопировать туда программу:
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
Dim nrow As Integer
Sub iter()
Const N =  5 
Dim ar(N) As Integer, lev As Integer
Cells.Clear
lev =  1 : ar(lev) =  1 
 1 :
For i =  1  To lev -  1 
   If ar(i) = ar(lev) Then
      If ar(lev) < N Then
         ar(lev) = ar(lev) +  1 
         GoTo  1 
      Else
         GoTo  2 
      End If
   End If
Next
If lev < N Then
   lev = lev +  1 
   ar(lev) =  1 
   GoTo  1 
Else
   s = ""
   For i =  1  To N
      s = s & ar(i)
   Next
   nrow = nrow +  1 
   Cells(nrow,  1 ) = s
End If
 2 :
lev = lev -  1 
If lev <  1  Then End
If ar(lev) < N Then
   ar(lev) = ar(lev) +  1 
   GoTo  1 
Else
    GoTo  2 
End If
End Sub
Sub recurs()
Const N =  5 
Dim ar(N) As Integer
Cells.Clear
per ar,  1 
End Sub
Sub per(ar() As Integer, ind As Integer)
Dim i As Integer, j As Integer, k As Integer, no_busy As Boolean
For i =  1  To UBound(ar)
   no_busy = True
   For j =  1  To ind -  1 
      If ar(j) = i Then
         no_busy = False
         Exit For
      End If
   Next
   If no_busy Then
      ar(ind) = i
      If ind < UBound(ar) Then
         per ar, ind +  1 
      Else
         s = ""
         For k =  1  To UBound(ar)
            s = s & ar(k)
         Next
         nrow = nrow +  1 
         Cells(nrow,  2 ) = s
      End If
   End If
Next
End Sub
...
Рейтинг: 0 / 0
25.03.2010, 10:38:53
| Ответить | Цитировать | Написать  
Что такое рекурсия, есть ли доходчивая инфа?
    #36541606
Фотография Gluk (Kazan)
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gluk (Kazan)
Участник
VowkРекурсивная форма получается меньше, но для понимания как бы сложнее.


Ага. это если ее на Васике писать.
Как то писал 8 ферзей на GW Basic, ваще мрак

А на схеме очень даже очевидно
...
Рейтинг: 0 / 0
25.03.2010, 11:07:52
| Ответить | Цитировать | Написать  
25 сообщений из 81, страница 2 из 4
  2  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Что такое рекурсия, есть ли доходчивая инфа?
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=16&msg=36541305&tid=1343758]:
 0ms
get settings:
 10ms
get forum list:
 15ms
check forum access:
 3ms
check topic access:
 3ms
track hit:
 186ms
get topic data:
 9ms
get forum data:
 2ms
get page messages:
 65ms
get tp. blocked users:
 1ms
others: 235ms
total:  529ms
созд. / загр.: 529ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]