ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Что такое рекурсия, есть ли доходчивая инфа?
81 сообщений из 81, показаны все 4 страниц
  все  
Что такое рекурсия, есть ли доходчивая инфа?
    #36531374
Bananas
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Bananas
Участник
Вики и прочее, что выдает гугл переварить не могу: то алгоритмы обработки информации, то примеры с зеркалами, то схема с замкнутым на себя контуром.. Короче не смог систематизировать. Есть ли нормальное описание рекурсии, а не ее частных случаев? Концепция или еще как-нибудь это назвать.
...
Рейтинг: 0 / 0
19.03.2010, 16:11:23
| Ответить | Цитировать | Написать  
Что такое рекурсия, есть ли доходчивая инфа?
    #36531389
Gwa
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gwa
Участник
Рекурсивная функция/процедура -это значит, что она вызывает сама себя.
...
Рейтинг: 0 / 0
19.03.2010, 16:14:23
| Ответить | Цитировать | Написать  
Что такое рекурсия, есть ли доходчивая инфа?
    #36531400
НачальнаяСтраница
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
НачальнаяСтраница
Гость
"Что бы понять рекурсию, нужно понять рекурсию" (с) Из сети.

Самый простой способ понять, это написать рекурсивный обход древовидной структуры. Что бы далеко не ходить за примерами, доберитесь из корня диска до спрятанного в глубинах папок файла.
...
Рейтинг: 0 / 0
19.03.2010, 16:17:37
| Ответить | Цитировать | Написать  
Что такое рекурсия, есть ли доходчивая инфа?
    #36531464
Фотография ML380
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ML380
Участник
GwaРекурсивная функция/процедура -это значит, что она вызывает сама себя.
Может вызывать сама себя, должно быть четко определено условия выхода из рекусии, иначе произойдет переполненние стека.
...
Рейтинг: 0 / 0
19.03.2010, 16:41:17
| Ответить | Цитировать | Написать  
Что такое рекурсия, есть ли доходчивая инфа?
    #36531488
egorych
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
egorych
Участник
ML380должно быть четко определено условия выхода из рекусии, иначе произойдет переполненние стека.переполнение стека может произойти и при чётком определении условия выхода. Условие выхода из рекурсии должно быть чётко определено, чтобы рекурсия завершилась хоть когда-нибудь.
...
Рейтинг: 0 / 0
19.03.2010, 16:47:39
| Ответить | Цитировать | Написать  
Что такое рекурсия, есть ли доходчивая инфа?
    #36531493
ShSerge
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ShSerge
Участник
У попа была собака, он её любил. Она съела кусок мяса. Он её убил. На могиле написал: "У попа была собака..." - это и есть рекурсия.
...
Рейтинг: 0 / 0
19.03.2010, 16:49:12
| Ответить | Цитировать | Написать  
Что такое рекурсия, есть ли доходчивая инфа?
    #36531500
Bananas
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Bananas
Участник
Тех.описание не подходит. Рекурсию не из пальца высосали, а сформулировали как результат наблюдения за чем-то реальным, имхо. Вот меня и интересует за чем, т.е. для решения каких задач ее можно применить.
...
Рейтинг: 0 / 0
19.03.2010, 16:51:25
| Ответить | Цитировать | Написать  
Что такое рекурсия, есть ли доходчивая инфа?
    #36531505
Gwa
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gwa
Участник
ShSergeУ попа была собака, он её любил. Она съела кусок мяса. Он её убил. На могиле написал: "У попа была собака..." - это и есть рекурсия.

Это как раз пример рекурсии без выхода, ведущей к переполнению стека..
...
Рейтинг: 0 / 0
19.03.2010, 16:52:58
| Ответить | Цитировать | Написать  
Что такое рекурсия, есть ли доходчивая инфа?
    #36531513
Gwa
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gwa
Участник
BananasТех.описание не подходит. Рекурсию не из пальца высосали, а сформулировали как результат наблюдения за чем-то реальным, имхо. Вот меня и интересует за чем, т.е. для решения каких задач ее можно применить.
А что, пример дерева каталогов, который тут упоминался Вам не понятен?
...
Рейтинг: 0 / 0
19.03.2010, 16:55:04
| Ответить | Цитировать | Написать  
Что такое рекурсия, есть ли доходчивая инфа?
    #36531522
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
BananasТех.описание не подходит. Рекурсию не из пальца высосали, а сформулировали как результат наблюдения за чем-то реальным, имхо. Вот меня и интересует за чем, т.е. для решения каких задач ее можно применить.
Если ты хоть раз успешно написал утилиту поиска файлов в каталогах и вложенных подкаталогах - то ты понял зачем нужна рекурсия.
...
Рейтинг: 0 / 0
19.03.2010, 16:58:19
| Ответить | Цитировать | Написать  
Что такое рекурсия, есть ли доходчивая инфа?
    #36531525
Bananas
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Bananas
Участник
Gwa
А что, пример дерева каталогов, который тут упоминался Вам не понятен?
Неа. Открыли папку, в ней открыли другую папку и так далее до папки с файлом. Не вижу, что тут такого.
...
Рейтинг: 0 / 0
19.03.2010, 16:59:26
| Ответить | Цитировать | Написать  
Что такое рекурсия, есть ли доходчивая инфа?
    #36531546
Gwa
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gwa
Участник
BananasGwa
А что, пример дерева каталогов, который тут упоминался Вам не понятен?
Неа. Открыли папку, в ней открыли другую папку и так далее до папки с файлом. Не вижу, что тут такого.

А что Вы хотели узреть ТАКОГО?
Ничего такого и нет.
На самом деле рекурсия очень простое понятие..
Ну скажем полиморфизм ООП -значительно сложнее.
Тут даже не о чем говорить, нужно хотя бы раз написать построение дерева в компоненте
TTreeView
Если же и после этого Вам будет непонятно, то считайте, что это безнадюга..
...
Рейтинг: 0 / 0
19.03.2010, 17:06:18
| Ответить | Цитировать | Написать  
Что такое рекурсия, есть ли доходчивая инфа?
    #36531553
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Bananasпапку, в ней открыли другую папку и так далее до папки с файлом. Не вижу, что тут такого.
Промах!

Ты этого не делал! Интерфейс файлового API не позволяет итеративно обходить все файлы на диске. Грубо говоря у тебя есть findfirst, findnext и функция проверки типа узла.

Не будь хвастуном а ПОПРОБУЙ это реализовать!
...
Рейтинг: 0 / 0
19.03.2010, 17:08:35
| Ответить | Цитировать | Написать  
Что такое рекурсия, есть ли доходчивая инфа?
    #36531591
tru55
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
tru55
Участник
BananasТех.описание не подходит. Рекурсию не из пальца высосали, а сформулировали как результат наблюдения за чем-то реальным, имхо. Вот меня и интересует за чем, т.е. для решения каких задач ее можно применить.

Насколько мне помнится, в книжках любили объяснять рекурсию на примере вычисления факториала
...
Рейтинг: 0 / 0
19.03.2010, 17:22:19
| Ответить | Цитировать | Написать  
Что такое рекурсия, есть ли доходчивая инфа?
    #36531610
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
tru55Насколько мне помнится, в книжках любили объяснять рекурсию на примере вычисления факториала
Да. Самый неудачный пример. Из той-же серии Числа Фибоначчи и т.п. Это скорее антипаттерны.
...
Рейтинг: 0 / 0
19.03.2010, 17:27:18
| Ответить | Цитировать | Написать  
Что такое рекурсия, есть ли доходчивая инфа?
    #36531638
Bananas
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Bananas
Участник
mayton,
не:) Значит я не корректно выразился. Я никогда обходов не писал -- написал, как представил процесс. А рекурсия изначально чем-то "изотерическим" воспринималась, типа результат глубокого постижения реальности:) Но все еще не могу четко понять в каких задачах можно применить рекурсию.
...
Рейтинг: 0 / 0
19.03.2010, 17:38:01
| Ответить | Цитировать | Написать  
Что такое рекурсия, есть ли доходчивая инфа?
    #36531666
Gwa
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Gwa
Участник
Bananasmayton,
не:) Значит я не корректно выразился. Я никогда обходов не писал -- написал, как представил процесс. А рекурсия изначально чем-то "изотерическим" воспринималась, типа результат глубокого постижения реальности:) Но все еще не могу четко понять в каких задачах можно применить рекурсию.

Из теории известно, что любой рекурсивный алгоритм можно реализовать без рекурсии.
Дерево тоже можно построить/обойти без рекурсии.
Но рекурсия в данном случае лучше, т.к. всё становится менее громоздким, более понятным и изящно выражает суть.
...
Рейтинг: 0 / 0
19.03.2010, 17:46:23
| Ответить | Цитировать | Написать  
Что такое рекурсия, есть ли доходчивая инфа?
    #36531678
pirovindos
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
pirovindos
Участник
Bananas,

Чтобы понять в каких задачах можно применить рекурсию нужно понять рекурсию.
А насчет глубоко понимания: например, попытка описать отношения в природе типа "предок-потомок" или в математике понятия "формула" некоторых привела к формулировке понятия рекурсии.

Хотя при для программной реализации рекурсивного алгоритма существует эквивалентная реализация без рекурсии (с циклом).
...
Рейтинг: 0 / 0
19.03.2010, 17:51:25
| Ответить | Цитировать | Написать  
Что такое рекурсия, есть ли доходчивая инфа?
    #36531690
Фотография Ggg_old
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Ggg_old
Участник
Это из математики пришло. Так легче и изящнее записываются некоторые формулы и определяются некоторые функции и понятия. В абстрактном мире математических абстракций никогда не переполняется стек, нет ошибок арифметического округления и нет переполнения разрядкой сетки. И да, память под массивы тоже никогда не кончается :)
...
Рейтинг: 0 / 0
19.03.2010, 17:55:48
| Ответить | Цитировать | Написать  
Что такое рекурсия, есть ли доходчивая инфа?
    #36531757
Факториал
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Факториал
Гость
Bananasmayton,
не:) Значит я не корректно выразился. Я никогда обходов не писал -- написал, как представил процесс. А рекурсия изначально чем-то "изотерическим" воспринималась, типа результат глубокого постижения реальности:) Но все еще не могу четко понять в каких задачах можно применить рекурсию.

Классика жанра нахождение факториала.

Факториал числа N+1 можно представить как факториал числа N умноженное на N

Factorial(N+1) = Factorial(N) * N.

Отсюда вывод, что факториал можно записать рекурсивной функцией.
Тоесть чтобы найти факториал для 10, нужно вызвать функцию факториала для 9 и умножить на 9.
Чтобы вычислить факториал 9, нужно вызвать функцию факториала для 8 и умножить на 8 и т.д.

Возникает вопрос, а что произойдет когда мы спустимся так до нахождения факториала 1 ?
А ничего, функция от факториала 1 будет возвращать всегда 1. Это и есть замыкание.
...
Рейтинг: 0 / 0
19.03.2010, 18:22:16
| Ответить | Цитировать | Написать  
Что такое рекурсия, есть ли доходчивая инфа?
    #36531806
Дональдак
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Дональдак
Участник
Факториал
Факториал числа N+1 можно представить как факториал числа N умноженное на N+1


И в примере нужно единичку к соответствующим множителям прибавить.
...
Рейтинг: 0 / 0
19.03.2010, 18:49:32
| Ответить | Цитировать | Написать  
Что такое рекурсия, есть ли доходчивая инфа?
    #36531832
Crazzy
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Crazzy
Участник
- Учитель, как мне определить расстояние до той горы?
- Сделай один шаг и будешь на шаг ближе.
...
Рейтинг: 0 / 0
19.03.2010, 19:06:48
| Ответить | Цитировать | Написать  
Что такое рекурсия, есть ли доходчивая инфа?
    #36531840
ShSerge
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ShSerge
Участник
А ещё есть теорема, что любую рекурсию можно прелбразовать в итерацию.
...
Рейтинг: 0 / 0
19.03.2010, 19:11:44
| Ответить | Цитировать | Написать  
Что такое рекурсия, есть ли доходчивая инфа?
    #36531949
Фотография Denis.
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Denis.
Участник
Салат рекурсивный: помидоры, огурцы, салат,...
...
Рейтинг: 0 / 0
19.03.2010, 20:40:28
| Ответить | Цитировать | Написать  
Что такое рекурсия, есть ли доходчивая инфа?
    #36532208
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
...
Рейтинг: 0 / 0
20.03.2010, 08:17:05
| Ответить | Цитировать | Написать  
Что такое рекурсия, есть ли доходчивая инфа?
    #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
| Ответить | Цитировать | Написать  
Что такое рекурсия, есть ли доходчивая инфа?
    #36541781
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
VowkКак справедливо тут говорилось, любой алгоритм можно записать как в рекурсивной, так и в итерационной форме. Рекурсивная форма получается меньше, но для понимания как бы сложнее.
Это фейк? Вы ТРАНСФОРМИРОВАЛИ рекурсивный алгоритм перестановок или взяли ДРУГОЙ ИТЕРАЦИОННЫЙ алгоритм. Я знаю такой существует. И он действительно проще для понимания чем метод с рекурсией.

(Я код не смотрел.)
...
Рейтинг: 0 / 0
25.03.2010, 12:03:43
| Ответить | Цитировать | Написать  
Что такое рекурсия, есть ли доходчивая инфа?
    #36542287
Vowk
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Vowk
Участник
maytonVowkКак справедливо тут говорилось, любой алгоритм можно записать как в рекурсивной, так и в итерационной форме. Рекурсивная форма получается меньше, но для понимания как бы сложнее.
Это фейк? Вы ТРАНСФОРМИРОВАЛИ рекурсивный алгоритм перестановок или взяли ДРУГОЙ ИТЕРАЦИОННЫЙ алгоритм. Я знаю такой существует. И он действительно проще для понимания чем метод с рекурсией.
(Я код не смотрел.)
Что сказать хотел?
...
Рейтинг: 0 / 0
25.03.2010, 14:17:19
| Ответить | Цитировать | Написать  
Что такое рекурсия, есть ли доходчивая инфа?
    #36542395
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
VowkЧто сказать хотел?
Обычно так не бывает. Рекурсивный алгоритм который занимает N строк исходного кода обычно (как правило) после трансформации его в плоский (НЕРЕКУРСИВНЫЙ) с использованием доп. структур данных типа стек, очередь, дек, может занимать более чем N строк. И это не свойство рекурсий а свойство самих языков программирования. Callback выглядит компактнее.

Если у тебя это не так, значит исходный алгоритм изначально НЕ БЫЛ рекурсивным.
...
Рейтинг: 0 / 0
25.03.2010, 14:45:11
| Ответить | Цитировать | Написать  
Что такое рекурсия, есть ли доходчивая инфа?
    #36542591
Альмалексия
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Альмалексия
Участник
Нафлудили 3 страницы, а толку? Автор такие глупые вопросы задаёт. Ему отвечают, а он опять спрашивает. Не дозрел человек значит.
...
Рейтинг: 0 / 0
25.03.2010, 15:34:37
| Ответить | Цитировать | Написать  
Что такое рекурсия, есть ли доходчивая инфа?
    #36542811
_мод
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
_мод
Гость
Gluk (Kazan)Как то писал 8 ферзей на GW Basic, ваще мрак
на клиппере. без рекурсии будет черт-те что
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
static pos[ 8 ],nr:= 1 
func main; return f8( 8 , 1 )
func f8(n,y)
  return if(n< 1 ,out(),if(y> 8 ,.f.,if(f1(y, 8 -n+ 1 ) .and. f8(n- 1 , 1 ),.t.,f8(n,y+ 1 ))))
func f1(y,x)
  local i
  for i= 1  to x- 1 
    if pos[i]=y .or. abs(y-pos[i])=abs(x-i); return .f.; end
  end
  pos[x]=y
  return .t.
func out
  local i,j
  ?nr++; ?''
  for i= 1  to  8 ; for j= 1  to  8 ; ??if(pos[j]=i,'X ','. '); end; ?''; end
  return .f.
...
Рейтинг: 0 / 0
25.03.2010, 16:40:04
| Ответить | Цитировать | Написать  
Что такое рекурсия, есть ли доходчивая инфа?
    #36545243
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MasterZiv
Участник
Модераторы, куда дели рекурсивный герб России ?

Модератор: В корзину.
...
Рейтинг: 0 / 0
26.03.2010, 16:51:55
| Ответить | Цитировать | Написать  
Что такое рекурсия, есть ли доходчивая инфа?
    #36545450
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MasterZiv
Участник
MasterZiv wrote:

> Модераторы, куда дели рекурсивный герб России ?
>
> *Модератор:* В корзину.

А с чего ?
Такое классное объяснение рекурсии ...
В чем проблема ?
Posted via ActualForum NNTP Server 1.4

Модератор: Объяснение классное, выбор картинки - не очень. Просто постарайтесь объяснять без использования официальных символов государства. На всякий случай :)
Спасибо за понимание.
...
Рейтинг: 0 / 0
26.03.2010, 18:11:50
| Ответить | Цитировать | Написать  
Что такое рекурсия, есть ли доходчивая инфа?
    #36546128
Фотография MasterZiv
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MasterZiv
Участник
MasterZiv wrote:

> *Модератор:* Объяснение классное, выбор картинки - не очень. Просто
> постарайтесь объяснять без использования официальных символов
> государства. На всякий случай :)
> Спасибо за понимание.

Не понимаю.

Вот из правил:


Публикация изображений.

Максимальный размер изображения, публикуемого с помощью кода img, должен
составлять не более 100 кб. Опубликованное изображение не должно носить
оскорбляющий характер.



Где написано, что нельзя использовать официальные символы государства ?

В чём вообще проблема, я не понимаю ?
Posted via ActualForum NNTP Server 1.4
...
Рейтинг: 0 / 0
27.03.2010, 13:39:46
| Ответить | Цитировать | Написать  
Что такое рекурсия, есть ли доходчивая инфа?
    #36546825
Bananas
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Bananas
Участник
АльмалексияАвтор такие глупые вопросы задаёт. Ему отвечают, а он опять спрашивает. Не дозрел человек значит.
Так ведь поэтому и задаю. Если человеку объяснить и он сразу поймет -- это значит только, что у него очень быстрый процесс "созревания", поэтому глупых вопросов либо 1-2, либо нет вообще.
По теме -- изначально сидело убеждение, что рекурсия применяется только к определенно структурированной информации. Особенно из-за примеров с картинками, стишком и зеркалами так думал. Теперь понял, что плясать нужно от задачи. Вчера как раз в тему про фракталы фильм смотрел. Тот же самый принцип: нахождение шаблона. В рекурсии -- одинаковых моментов в алгоритме задачи, в фракталах -- одинаковых моментов в изображении.
Теперь только руку набить осталось в определении рекурсивных алгоритмов. Случаем задачников таких не существует для обучения? :) Типа как в судоку: легко, средне, сложно?
...
Рейтинг: 0 / 0
28.03.2010, 14:41:22
| Ответить | Цитировать | Написать  
Что такое рекурсия, есть ли доходчивая инфа?
    #36546865
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Из инженерной графики: Снежинка Коха, Множество Мандельбротта, Кривая Гилберта, Кривая Серпинского, Лист Папоротника, Различные алгоритмы генерации лабиринтов (Maze), Фрактальное сжатие изображение.

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

Игровые задачи: Решение (solve) шахматных, шашечных и прочих настольных задач, ханойские башни, головоломки, кубики-рубики, пентамино, раскройка, укладка рюкзаков.

Около-научные задачи: генетические проблемы, поиск лекарств "от всего".

Разработка трансляторов : парсеры, BNF, Yacc, Bizon, XML/XPath.
...
Рейтинг: 0 / 0
28.03.2010, 15:11:22
| Ответить | Цитировать | Написать  
Что такое рекурсия, есть ли доходчивая инфа?
    #36546890
Фотография Roman S. Golubin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Roman S. Golubin
Участник
GwaShSergeУ попа была собака, он её любил. Она съела кусок мяса. Он её убил. На могиле написал: "У попа была собака..." - это и есть рекурсия.

Это как раз пример рекурсии без выхода, ведущей к переполнению стека..

Не всякая рекурсия без выхода ведет к переполнению стека
...
Рейтинг: 0 / 0
28.03.2010, 15:49:44
| Ответить | Цитировать | Написать  
Что такое рекурсия, есть ли доходчивая инфа?
    #36547002
Фотография ZyK_BotaN
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ZyK_BotaN
Участник
в дополнение к предыдущему оратору, стек - только один из инструментов реализации рекурсии.
Для реализации рекурсии порождающей итеративный процесс, в энергичных
языках используют хвостовую рекурсию.ЕМНИП, в ленивых даже не нужно аккумулятор
использовать, там сборщик мусора сам все проблемы решает.
а если учесть что рекурсия понятие математическое(философское если хотите), то
стек, память и время выполнения - имеет мало общего с этим понятием.
...
Рейтинг: 0 / 0
28.03.2010, 18:20:33
| Ответить | Цитировать | Написать  
Что такое рекурсия, есть ли доходчивая инфа?
    #36547099
egorych
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
egorych
Участник
ZyK_BotaNа если учесть что рекурсия понятие математическое(философское если хотите), то
стек, память и время выполнения - имеет мало общего с этим понятием.до тех пор, пока алгоритм существует на бумаге - да, если же он воплощается в программный код, то, к сожалению, стек, память и прочая "мутота" вылезают на поверхность во всей своей неприглядности =)))
...
Рейтинг: 0 / 0
28.03.2010, 20:07:39
| Ответить | Цитировать | Написать  
Что такое рекурсия, есть ли доходчивая инфа?
    #36548998
Фотография k0rvin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
k0rvin
Участник
рекурсия -- это рекурсия
...
Рейтинг: 0 / 0
29.03.2010, 19:01:09
| Ответить | Цитировать | Написать  
Что такое рекурсия, есть ли доходчивая инфа?
    #36559166
junior idiot
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
junior idiot
Гость
Все эти обычные слова навроде "рекурсия -- это вызов функцией самой себя" никакого понимания не дают, а пытливого человека могут лишь запутать.

Ну как можно "вызвать" функцию, которая ещё не определена, то есть ещё неизвестно, что она из себя представляет и какой процесс вычислений задаёт? То есть, рекурсия требует более широкого представления об определении функций , ближе к математическому, нежели традиционно-примитивному как последовательности инструкций компьютеру вперемежку с вызовами ранее определённых функций как "макросов" для таких же по сути последовательностей инструкций, и по этой причине слово "вызов" использовать нехорошо -- "вызывать" нечего.

Для именно "программистского" понимания рекурсии, как её себе представлять и в каких терминах о ней думать, можно порекомендовать весьма короткую и ориентированную именно на понимание лекцию о естественной связи рекурсивных функций в программах и комбинатором неподвижной точки .

Непосредственно же реализация возможности рекурсивных вызовов (в компиляторах, виртуальных машинах и т.п.), так же как и всякие оптимизации хвостовых вызовов и т.п. -- вопросы скорее технического характера, самого понимания "рекурсии" мало касающиеся.
...
Рейтинг: 0 / 0
03.04.2010, 13:15:32
| Ответить | Цитировать | Написать  
Что такое рекурсия, есть ли доходчивая инфа?
    #36559241
avb1003
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
avb1003
Участник
junior idiot...
Ну как можно "вызвать" функцию, которая ещё не определена, то есть ещё неизвестно, что она из себя представляет и какой процесс вычислений задаёт?
...Самым обычным способом. Функции в каком-то смысле и были придуманы для того, чтобы можно было ими пользоваться, "не зная, что они из себя представляет". Именно так и используется подавляющее большинство системных , библиотечных ф-й или функций созданных другими программистами. Именно на этом основано программирование "сверху вниз" - применение или вызовы функций пишутся до реализации этих функций. Причем это фактическое применение может дополнять (или иногда даже замещать) техническое задание и т.д., когда функции нижнего уровня пишутся другим программистом.
...
Рейтинг: 0 / 0
03.04.2010, 15:41:29
| Ответить | Цитировать | Написать  
Что такое рекурсия, есть ли доходчивая инфа?
    #36559245
junior idiot
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
junior idiot
Гость
avb1003 ,
Использование функций, детали реализации которых в данный момент не важны , и использование функций, детали реализации которых в данный момент как раз и описываются -- принципиально разные вещи, ничего общего не имеющие.
Первое совершенно очевидным образом возможно без именования функций (то есть связывания некоторого процесса вычислений с определённым символом): достаточно просто оставлять пробелы, в которые потом вписывать детализирующий код.
А вот что делать с рекурсией без возможности именовать функции? Здесь выход совершенно не так очевиден.
А вопрос этот вполне естественный, ведь интуитивно ясно, что "функция", что бы ни подразумевалось под этим словом, никак не должна зависеть от каких-то там наименований и условных обозначений.
...
Рейтинг: 0 / 0
03.04.2010, 15:51:01
| Ответить | Цитировать | Написать  
Что такое рекурсия, есть ли доходчивая инфа?
    #36559266
avb1003
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
avb1003
Участник
junior idiot avb1003 ,
Использование функций, детали реализации которых в данный момент не важны , и использование функций, детали реализации которых в данный момент как раз и описываются -- принципиально разные вещи, ничего общего не имеющие.
...Это только на Ваш взглядjunior idiot...
Первое совершенно очевидным образом возможно без именования функций (то есть связывания некоторого процесса вычислений с определённым символом): достаточно просто оставлять пробелы, в которые потом вписывать детализирующий код.Это вообще мимо. Именование функции, число и тип параметров должны быть уже известны. То есть вызов должен делаться после "объявления функции", как это называется в книжках по С++.junior idiot...
А вот что делать с рекурсией без возможности именовать функции? Кажется, что Вы никогда не писали никаких функций, так как придумываете несуществующие проблемы. Кто лишил Вас возможности "именовать" функцию? junior idiot ...
Здесь выход совершенно не так очевиден.Начните что-нибудь программировать и все станет гораздо очевиднее.junior idiot...
А вопрос этот вполне естественный, ведь интуитивно ясно, что "функция", что бы ни подразумевалось под этим словом, никак не должна зависеть от каких-то там наименований и условных обозначений.Здесь вообще непонятно, что Вы хотели сказать. В данном контексте функция или же подпрограмма просто "поименованная или иным образом идентифицированная часть компьютерной программы, содержащая описание определённого набора действий...." См. Подпрограмма или Функция (программирование)
...
Рейтинг: 0 / 0
03.04.2010, 16:57:11
| Ответить | Цитировать | Написать  
Что такое рекурсия, есть ли доходчивая инфа?
    #36559287
junior idiot
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
junior idiot
Гость
avb1003Это вообще мимо. Именование функции, число и тип параметров должны быть уже известны. То есть вызов должен делаться после "объявления функции", как это называется в книжках по С++.
Вызов чего , простите? Имени, числа и типов параметров?
Хе-хе.

avb1003Начните что-нибудь программировать и все станет гораздо очевиднее.
Ну, давайте попробую.
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
> (((lambda (f)
     ((lambda (x)
        (f (lambda (y) ((x x) y))))
      (lambda (x)
        (f (lambda (y) ((x x) y))))))
   (lambda (fact) 
     (lambda (n) 
       (if (eq? n  0 )  1 
           (* n (fact (- n  1 )))))))
    10 )

 3628800
Смотрите-ка, получилось (10! = 3628800). Функция рекурсивная, алгоритм её вычисления рекурсивный, а именованных функций нет, одни анонимные лямбды.
Но разве такое преобразование очевидно? И уж тем более его вычислительный смысл? Мне -- нет. Подумать есть над чем, вполне.

avb1003Здесь вообще непонятно, что Вы хотели сказать. В данном контексте функция или же подпрограмма просто "поименованная или иным образом идентифицированная часть компьютерной программы, содержащая описание определённого набора действий...."
Именно, набор действий . Но "объявленная функция" (что Вы считаете достаточным для её вызова) ещё не является ни действием ни набором действий -- она лишь имя и ничего более. Так на каком основании она может являться частью подпрограммы?
Можно, конечно, априорно обозвать рекурсивную функцию "действием", тогда определение вполне удовлетворяется. Только такой тип рассуждений в логике называется "порочный круг" и на практике может привести к ошибкам. А может и не привести (как в данном случае).

Вряд ли кто-то сомневается, что вполне можно пользоваться рекурсией, не обладая пониманием того, что это такое. Но, как мне показалось, топик как раз о том, что это такое , а не как этим пользоваться .
...
Рейтинг: 0 / 0
03.04.2010, 17:39:47
| Ответить | Цитировать | Написать  
Что такое рекурсия, есть ли доходчивая инфа?
    #36559290
junior idiot
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
junior idiot
Гость
Эх, самое главное-то пропустил я.
avb1003придумываете несуществующие проблемы. Кто лишил Вас возможности "именовать" функцию?
Меня -- никто. Но функция, являясь лишь "набором действий", вовсе не обязана обладать именем. Ведь не обязана? Конечно, не обязана, и анонимные функции нынче очень широко используются, да и наивно было бы думать, что процессор что-то знает про то, как там была названа в коде та или иная функция -- foo() или bar().
Следовательно, должна быть возможность абстрагироваться от имени функции и от процесса именования вообще. Если такой возможности я не вижу, то это означает, что связь между моим кодом и процессом его исполнения компьютером для меня не ясна.
...
Рейтинг: 0 / 0
03.04.2010, 17:43:52
| Ответить | Цитировать | Написать  
Что такое рекурсия, есть ли доходчивая инфа?
    #36559361
avb1003
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
avb1003
Участник
junior idiotЭх, самое главное-то пропустил я.
avb1003придумываете несуществующие проблемы. Кто лишил Вас возможности "именовать" функцию?
Меня -- никто. Но функция, являясь лишь "набором действий", вовсе не обязана обладать именем. Ведь не обязана? ...Именем не обязана. Если функция вызывается только из одно места, то это даже может быть удобно - не давать имени функции, если этого не нужно. Perl, например, предоставляет эту возможность. Но в определении, которое я привел написано: "...или иным образом идентифицированная часть компьютерной программы...", то есть, что-то вроде адреса у нее обязательно есть.junior idiot...... Конечно, не обязана, и анонимные функции нынче очень широко используются, да и наивно было бы думать, что процессор что-то знает про то, как там была названа в коде та или иная функция -- foo() или bar() ...А так никто и не думает. Процессор "знает" только команды, котороые он обязан выполнять.junior idiot...
Следовательно, должна быть возможность абстрагироваться от имени функции и от процесса именования вообще. ... У Вас никто не отнимает возможности, например, поработать процессором. Но стоит ли? Абстракции, имена и т.п. вводятся(по крайней мере, как правило) для облегчения задачи, а вовсе не для того, чтобы запутать/обмануть неофитов. junior idiot...Если такой возможности я не вижу, то это означает, что связь между моим кодом и процессом его исполнения компьютером для меня не ясна.С этим спорить почти невозможно. Разве что с помощью детектора лжи и т.п. Вот когда кто-то говорит, что ему все ясно, тут гораздо больше возможности доказать обратное, если этот кто-то ошибается.
...
Рейтинг: 0 / 0
03.04.2010, 20:11:00
| Ответить | Цитировать | Написать  
Что такое рекурсия, есть ли доходчивая инфа?
    #36559405
Фотография k0rvin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
k0rvin
Участник
avb1003Именем не обязана. Если функция вызывается только из одно места, то это даже может быть удобно - не давать имени функции, если этого не нужно. Perl, например, предоставляет эту возможность.

это не единственное применение и далеко не только перл предоставляет такую возможность.

avb1003
Но в определении, которое я привел написано: "...или иным образом идентифицированная часть компьютерной программы...", то есть, что-то вроде адреса у нее обязательно есть.
это определение функций как подпрограмм, что свойствено императивному подходу и старым процедурным языкам. в функциональном функции не являются "подрограммами" в этом смысле.
...
Рейтинг: 0 / 0
03.04.2010, 21:15:20
| Ответить | Цитировать | Написать  
Что такое рекурсия, есть ли доходчивая инфа?
    #36559413
Фотография k0rvin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
k0rvin
Участник
k0rvin
это не единственное применение
например с помощью анонимных функций можно моделировать типы данных, например "пару" (Сассман в видео SICP назвал этот приём "хаком Черча" =)):

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
(define (make-pair x y)
  (lambda (m) (m x y)))

(define (first pair)
  (pair (lambda (x y) x)))

(define (second pair)
  (pair (lambda (x y) y)))

;;; Testing:

(define a (make-pair  1   2 )) ; =>  #<procedure> ; implementation dependent

(first a) ; =>  1 

(second a) ; =>  2
...
Рейтинг: 0 / 0
03.04.2010, 21:25:56
| Ответить | Цитировать | Написать  
Что такое рекурсия, есть ли доходчивая инфа?
    #36559437
Constantine Voronin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Constantine Voronin
Гость
Рекурсия - это рекурсия.
...
Рейтинг: 0 / 0
03.04.2010, 21:56:19
| Ответить | Цитировать | Написать  
Что такое рекурсия, есть ли доходчивая инфа?
    #36559972
avb1003
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
avb1003
Участник
k0rvinavb1003Именем не обязана. Если функция вызывается только из одно места, то это даже может быть удобно - не давать имени функции, если этого не нужно. Perl, например, предоставляет эту возможность.

это не единственное применение и далеко не только перл предоставляет такую возможность.А где Вы увидели про единственность или про исключительность Perl?k0rvin

avb1003
Но в определении, которое я привел написано: "...или иным образом идентифицированная часть компьютерной программы...", то есть, что-то вроде адреса у нее обязательно есть.
это определение функций как подпрограмм, что свойствено императивному подходу и старым процедурным языкам. в функциональном функции не являются "подрограммами" в этом смысле.Ну и что, что "... императивному...", что "... старым ..." или "... процедурным ..." ? Отвечая на вопрос, я думал оказать промощь тому , кто, как мне показалось, действительно зашел в тупик от бессмысленных размышелений, а вовсе не пытался изрекать истину в последней инстанции, тем более мерятся длиной "выступающих частей тела". Да, я не являюсь специалистом по языку Лисп, хотя и прочитал книгу по нему, смотрел примеры и т.д. и когда в начале 90-х мне, тогда программисту на Фортране, понадобились дополнительные члены в каких-то формулах из учебников, я сам их нашел с помощью какой-то Лисп-подобной системы. Не помню точно, но кажется это был MuMATH Но, повторяю, я не являюсь специалистом по Лисп и не готов комментировать/давать советы. По крайней мере бесплатно и на этом форуме. Могу только предположить, IMHO конечно, что человеку испытывающими проблемы с Лисп, имеет смысл заняться чем-то попроще - например, программированием на Фортране. Или на Perl, что с моей точки зрения полезней и интересней. Опять-таки IMHO.
...
Рейтинг: 0 / 0
04.04.2010, 18:25:13
| Ответить | Цитировать | Написать  
Что такое рекурсия, есть ли доходчивая инфа?
    #36564224
Фотография k0rvin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
k0rvin
Участник
avb1003,

казалось бы, при чем тут Лисп? пример демонстрирует лямбда-исчисление. не понятен синтаксис Scheme? можно и на Haskell:

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
[ ~ ] ghci
GHCi, version  6 . 10 . 4 : http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer ... linking ... done.
Loading package base ... linking ... done.
Prelude> let makePair x y m = m x y
Prelude> let first pair = pair $ \x y -> x
Prelude> let second pair = pair $ \x y -> y
Prelude> let a = makePair  1   2 
Prelude> first a
 1 
Prelude> second a
 2 
Prelude>
...
Рейтинг: 0 / 0
06.04.2010, 18:43:15
| Ответить | Цитировать | Написать  
Что такое рекурсия, есть ли доходчивая инфа?
    #36564337
avb1003
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
avb1003
Участник
k0rvinavb1003,

казалось бы, при чем тут Лисп? пример демонстрирует лямбда-исчисление. не понятен синтаксис Scheme? ...Где я писал, что мне непонятен какой-то синтаксис? Вот когда у меня будет вопрос по синтаксису Scheme, Haskel или еще там чего, и я сочту необходимым/целесообразным попросить помощи на этом форуме, вот тогда сможете продемонстрировать свои знания. Пока же в этом нет никакой необходимости. В данном случае я имею в виду, конечно, только себя. Кому-то может быть и интересно, что тoварищ X может написать пару строк на языке Y. Да, то что у меня нет вопросов по синтаксису, вовсе не означает, что я cмогу/захочу отвечать на такие вопросы и тем более не означает, что мне известен синтаксис всех языков и т.д.k0rvin... можно и на Haskell:

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
[ ~ ] ghci
GHCi, version  6 . 10 . 4 : http://www.haskell.org/ghc/  :? for help
Loading package ghc-prim ... linking ... done.
Loading package integer ... linking ... done.
Loading package base ... linking ... done.
Prelude> let makePair x y m = m x y
Prelude> let first pair = pair $ \x y -> x
Prelude> let second pair = pair $ \x y -> y
Prelude> let a = makePair  1   2 
Prelude> first a
 1 
Prelude> second a
 2 
Prelude>
Ну и что? Чего хотите сказать-то? Своими словами можете? На скольких еще языках Вы сможете воспроизвести данный "шедевр"?
...
Рейтинг: 0 / 0
06.04.2010, 19:49:36
| Ответить | Цитировать | Написать  
Что такое рекурсия, есть ли доходчивая инфа?
    #36564473
Фотография k0rvin
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
k0rvin
Участник
avb1003,

тогда объясните, к чему вообще Ваши коментарии?
...
Рейтинг: 0 / 0
06.04.2010, 21:20:25
| Ответить | Цитировать | Написать  
Что такое рекурсия, есть ли доходчивая инфа?
    #36564595
avb1003
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
avb1003
Участник
k0rvinavb1003,

тогда объясните, к чему вообще Ваши коментарии?Я уже объяснял. Читайте внимательней.
...
Рейтинг: 0 / 0
06.04.2010, 23:16:11
| Ответить | Цитировать | Написать  
Что такое рекурсия, есть ли доходчивая инфа?
    #36574451
henry
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
henry
Участник
ShSergeУ попа была собака, он её любил. Она съела кусок мяса. Он её убил. На могиле написал: "У попа была собака..." - это и есть рекурсия.
Здесь выхода нет.
...
Рейтинг: 0 / 0
12.04.2010, 15:59:51
| Ответить | Цитировать | Написать  
Что такое рекурсия, есть ли доходчивая инфа?
    #36574558
Naf
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Naf
Участник
Рекурсия
С уважением, Naf
...
Рейтинг: 0 / 0
12.04.2010, 16:29:22
| Ответить | Цитировать | Написать  
81 сообщений из 81, показаны все 4 страниц
  все  
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Что такое рекурсия, есть ли доходчивая инфа?
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?all=1&fid=16&tid=1343758]:
 0ms
get settings:
 10ms
get forum list:
 15ms
check forum access:
 2ms
check topic access:
 2ms
track hit:
 176ms
get topic data:
 9ms
get forum data:
 2ms
get page messages:
 101ms
get tp. blocked users:
 1ms
others: 240ms
total:  558ms
созд. / загр.: 558ms
x
x
Закрыть


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