Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 4.93/56: Рейтинг темы: голосов - 56, средняя оценка - 4.93
0 / 0 / 0
Регистрация: 24.06.2013
Сообщений: 55
1

Что такое рекурсия? Зачем она нужна?

02.07.2013, 19:52. Показов 10927. Ответов 41
Метки нет (Все метки)

Объясните пож человеческим языком, что такое Рекурсия.

Я знаю что это вызов функции самой себя.
Но всё равно не могу догнать зачем она нужна.

Заранее спасибо!
0

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

Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
02.07.2013, 19:52
Ответы с готовыми решениями:

Что такое виртуальная функция и зачем она нужна?
Мне с трудом пришлось понять, пока не прочитал книгу и не проработал код на виртуальных функциях....

Что такое тестирующая программа и зачем она нужна?
Есть задание, Написать функцию для перевода переменной типа long в символьную строку в двоичном...

Что делает функция compare в коде и зачем она нужна в qsort
Объясните, пожалуйста, что делает функция compare (17 строка) в данном случае и зачем она нужна в...

Явная специализация, зачем она нужна?(Шаблоны функций)
Какой смысл в явной специализации, когда есть перегрузка? если можно, и примерчик) я себе уже в...

41
118 / 80 / 1
Регистрация: 10.08.2011
Сообщений: 664
02.07.2013, 20:00 2
Это одно из многих определений в учебниках, которое крайне редко используется на практике.
В педевикии лаконично описано, но маловероятно повстречать сие в реалиях.
0
Эксперт С++
4258 / 2232 / 203
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
02.07.2013, 20:04 3
Цитата Сообщение от Second Посмотреть сообщение
маловероятно повстречать сие в реалиях.
да ну... та же широко используемая сортировка quicksort рекурсивная. обработка бинарных деревьев чаше всего рекурсивна и многое другое.
0
0 / 0 / 0
Регистрация: 24.06.2013
Сообщений: 55
02.07.2013, 20:10  [ТС] 4
Цитата Сообщение от Thinker Посмотреть сообщение
да ну... та же широко используемая сортировка quicksort рекурсивная. обработка бинарных деревьев чаше всего рекурсивна и многое другое.
расскажите о рекурсии по подробнее пож
0
187 / 180 / 25
Регистрация: 27.01.2012
Сообщений: 1,335
02.07.2013, 20:16 5
sancho1996, это просто вызов функции самой себя. Допустим:
C++
1
2
3
4
5
6
bool f(int x)
{
if (x == 1) return false;
else
f(x - 1);
}
Функция будет вызывать себя -ндцать раз, до тех пор пока не вызовет с числом, равным 1, а затем вызов прекратится.
1
Эксперт С++
4967 / 3074 / 456
Регистрация: 10.11.2010
Сообщений: 11,160
Записей в блоге: 10
02.07.2013, 20:40 6
Много лишнего для примера..
C++
1
2
3
4
5
void func( int n )
{
    if ( !n ) return; // если n == 0 ...
    func( n - 1 );
}
Собственно, она ничего не делает, просто пример работы рекурсии.
0
Эксперт С++
4258 / 2232 / 203
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
02.07.2013, 20:45 7
Цитата Сообщение от lazybiz Посмотреть сообщение
она ничего не делает, просто пример работы рекурсии.
вот откуда потом появляются фразы типа

Цитата Сообщение от Second Посмотреть сообщение
Это одно из многих определений в учебниках, которое крайне редко используется на практике... маловероятно повстречать сие в реалиях.
0
castaway
02.07.2013, 20:52
  #8

Не по теме:

Thinker, ))))))

0
99 / 52 / 27
Регистрация: 21.05.2012
Сообщений: 1,170
13.05.2017, 09:18 9
Цитата Сообщение от Thinker Посмотреть сообщение
да ну... та же широко используемая сортировка quicksort рекурсивная. обработка бинарных деревьев чаше всего рекурсивна и многое другое.
Подскажите нужна ли рекурсия в С++
ЕСЛИ её можно заменить for ?
0
667 / 213 / 88
Регистрация: 21.07.2016
Сообщений: 1,036
Записей в блоге: 2
13.05.2017, 11:29 10
Цитата Сообщение от eXPonent Посмотреть сообщение
Подскажите нужна ли рекурсия в С++
ЕСЛИ её можно заменить for ?
очевидно же что нет, ибо stack overflow!
0
Просто Лис
Эксперт Python
4300 / 2710 / 914
Регистрация: 17.05.2012
Сообщений: 8,028
Записей в блоге: 9
13.05.2017, 11:47 11
Цитата Сообщение от eXPonent Посмотреть сообщение
ЕСЛИ её можно заменить for ?
Цитата Сообщение от Thinker Посмотреть сообщение
обработка бинарных деревьев чаше всего рекурсивна
Мне даже интересно стало, как вы будете обходить дерево, используя цикл
1
Модератор
Эксперт CЭксперт С++
4450 / 4031 / 749
Регистрация: 07.10.2015
Сообщений: 8,433
13.05.2017, 12:57 12
sancho1996, рекурсия используется для работы с данными, у которых структура (объект)
содержит вложенный объект, структурно аналогичный самому себе или (что бывает чаще) ссылку на такой же объект.
И тогда для работы с вложенным объектом просто вызываем самого себя, но с новыми параметрами.
Подобная структура объектов удобно тем, что так можно описать потенциально бесконечную структуру данных.
Подобные структуры используются при описании списков и графов, тех же деревьев.
1
Эксперт C
25693 / 16043 / 3441
Регистрация: 24.12.2010
Сообщений: 35,110
13.05.2017, 13:28 13
Цитата Сообщение от eXPonent Посмотреть сообщение
Подскажите нужна ли рекурсия в С++
ЕСЛИ её можно заменить for ?
В принципе, без рекурсии можно обойтись. Вот, Дональд Кнут в своей классической монографии "Искусство программирования" всячески рекурсии избегает. И для задач, в которых рекурсия просто напрашивается (не вычисление факториала! ) просто моделирует стеки. В итоге его алгоритмы выглядят на порядок более громоздкими, чем могли бы быть.

Добавлено через 3 минуты
Ну, а класс задач, в которых применение рекурсии естественно, кратко описал уважаемый _liv_.
А вообще-то и без циклов for можно обойтись, и вообще без циклов. Есть же goto
2
99 / 52 / 27
Регистрация: 21.05.2012
Сообщений: 1,170
13.05.2017, 14:14 14

Не по теме:

согласен в ассемблере без джампа никак) он по всюду



А об рекурсии я имел ввиду, что она часто память жрут сильно много, даже грамотно написанные, а особенно если случайно допустил ошибку и она сожрет её всю
0
Модератор
Эксперт CЭксперт С++
4450 / 4031 / 749
Регистрация: 07.10.2015
Сообщений: 8,433
13.05.2017, 14:20 15
Цитата Сообщение от eXPonent Посмотреть сообщение
грамотно написанные
Грамотно написанные - грамотно используют память.
Кривые руки любую программу введут в ступор...
Любой метод - неуниверсален. К каждому типу задач необходимо пременять свой подход.
Рекурсия - не панацея, но порой без нее не обойтись, точнее, без нее намного сложнее...
0
Эксперт C
25693 / 16043 / 3441
Регистрация: 24.12.2010
Сообщений: 35,110
13.05.2017, 14:20 16
Цитата Сообщение от eXPonent Посмотреть сообщение
а особенно если случайно допустил ошибку и она сожрет её всю
Если допустил ошибку, то и без рекурсии будешь сожран.
0
99 / 52 / 27
Регистрация: 21.05.2012
Сообщений: 1,170
13.05.2017, 14:22 17
Цитата Сообщение от _liv_ Посмотреть сообщение
потенциально бесконечную структуру данных.
можно примеры?
как все данные должны быть конечными, иначе их вес будет бесконечным

Добавлено через 15 секунд
Цитата Сообщение от _liv_ Посмотреть сообщение
потенциально бесконечную структуру данных.
можно примеры?
как все данные должны быть конечными, иначе их вес будет бесконечным
0
2408 / 1810 / 398
Регистрация: 15.12.2013
Сообщений: 7,826
13.05.2017, 14:23 18
Цитата Сообщение от eXPonent Посмотреть сообщение
А об рекурсии я имел ввиду, что она часто память жрут сильно много, даже грамотно написанные, а особенно если случайно допустил ошибку и она сожрет её всю
В C++ компиляторы уже давно умеют в оптимизацию хвостовой рекурсии.
0
Модератор
Эксперт CЭксперт С++
4450 / 4031 / 749
Регистрация: 07.10.2015
Сообщений: 8,433
13.05.2017, 14:27 19
Цитата Сообщение от eXPonent Посмотреть сообщение
как все данные должны быть конечными, иначе их вес будет бесконечным
Я ж сказал "потенциально бесконечную", т.е. конечную, но сколько позволяет архитектура
0
Одессит
240 / 86 / 43
Регистрация: 30.12.2013
Сообщений: 316
Записей в блоге: 2
13.05.2017, 16:58 20
Цитата Сообщение от eXPonent Посмотреть сообщение
Подскажите нужна ли рекурсия в С++
ЕСЛИ её можно заменить for ?
Макконелл советует обходиться без рекурсии, если это возможно. Код становится более понятным и меньше возможностей сделать ошибку, например переполнение стека.
1
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
13.05.2017, 16:58

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

ООП: Зачем нужна таблица виртуальных методов? Она замедляет работу программы
Разве нельзя определить, метод какого класса вызывать во время компиляции?

сегодня наконец то понял что такое КЛАСС, и ОБЪЕКТ. понято всё, кроме одного - зачем всё это? в смысле, можно же без этого? так зачем жизнь усложнять?
сегодня наконец то понял что такое КЛАСС, и ОБЪЕКТ. понято всё, кроме одного - зачем всё это? в...

Кто-нибудь может подробно объяснить, что такое allocators, зачем это и что с ними делать? Нигде не нашёл инфы
Заранее спасибо.

Что такое hash-таблицы, и зачем они нужны?
Обьясните пожалуста по простому что такое хеш таблици и зачем они надо... пытался разобратся с ними...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.