Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
sancho1996
0 / 0 / 0
Регистрация: 24.06.2013
Сообщений: 55
#1

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

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

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

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

Заранее спасибо!
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
02.07.2013, 19:52     Что такое рекурсия? Зачем она нужна?
Посмотрите здесь:
Что такое тестирующая программа и зачем она нужна? C++
Что такое виртуальная функция и зачем она нужна? C++
Что делает функция compare в коде и зачем она нужна в qsort C++
Явная специализация, зачем она нужна?(Шаблоны функций) C++
C++ Что такое hash-таблицы, и зачем они нужны?
Битовые поля структур: что такое и зачем они нужны? C++
C++ Что делает данный код и зачем такое кому-нибудь может понадобиться?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Second
79 / 80 / 1
Регистрация: 10.08.2011
Сообщений: 665
02.07.2013, 20:00     Что такое рекурсия? Зачем она нужна? #2
Это одно из многих определений в учебниках, которое крайне редко используется на практике.
В педевикии лаконично описано, но маловероятно повстречать сие в реалиях.
Thinker
Эксперт C++
4221 / 2195 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
02.07.2013, 20:04     Что такое рекурсия? Зачем она нужна? #3
Цитата Сообщение от Second Посмотреть сообщение
маловероятно повстречать сие в реалиях.
да ну... та же широко используемая сортировка quicksort рекурсивная. обработка бинарных деревьев чаше всего рекурсивна и многое другое.
sancho1996
0 / 0 / 0
Регистрация: 24.06.2013
Сообщений: 55
02.07.2013, 20:10  [ТС]     Что такое рекурсия? Зачем она нужна? #4
Цитата Сообщение от Thinker Посмотреть сообщение
да ну... та же широко используемая сортировка quicksort рекурсивная. обработка бинарных деревьев чаше всего рекурсивна и многое другое.
расскажите о рекурсии по подробнее пож
nexen
187 / 180 / 3
Регистрация: 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, а затем вызов прекратится.
castaway
Эксперт С++
4880 / 3016 / 370
Регистрация: 10.11.2010
Сообщений: 11,076
Записей в блоге: 10
Завершенные тесты: 1
02.07.2013, 20:40     Что такое рекурсия? Зачем она нужна? #6
Много лишнего для примера..
C++
1
2
3
4
5
void func( int n )
{
    if ( !n ) return; // если n == 0 ...
    func( n - 1 );
}
Собственно, она ничего не делает, просто пример работы рекурсии.
Thinker
Эксперт C++
4221 / 2195 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
02.07.2013, 20:45     Что такое рекурсия? Зачем она нужна? #7
Цитата Сообщение от lazybiz Посмотреть сообщение
она ничего не делает, просто пример работы рекурсии.
вот откуда потом появляются фразы типа

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

Не по теме:

Thinker, ))))))

eXPonent
48 / 48 / 2
Регистрация: 21.05.2012
Сообщений: 1,067
13.05.2017, 09:18     Что такое рекурсия? Зачем она нужна? #9
Цитата Сообщение от Thinker Посмотреть сообщение
да ну... та же широко используемая сортировка quicksort рекурсивная. обработка бинарных деревьев чаше всего рекурсивна и многое другое.
Подскажите нужна ли рекурсия в С++
ЕСЛИ её можно заменить for ?
dailydose
overmind
347 / 94 / 25
Регистрация: 21.07.2016
Сообщений: 470
13.05.2017, 11:29     Что такое рекурсия? Зачем она нужна? #10
Цитата Сообщение от eXPonent Посмотреть сообщение
Подскажите нужна ли рекурсия в С++
ЕСЛИ её можно заменить for ?
очевидно же что нет, ибо stack overflow!
Рыжий Лис
Просто Лис
249 / 204 / 54
Регистрация: 17.05.2012
Сообщений: 792
Записей в блоге: 4
13.05.2017, 11:47     Что такое рекурсия? Зачем она нужна? #11
Цитата Сообщение от eXPonent Посмотреть сообщение
ЕСЛИ её можно заменить for ?
Цитата Сообщение от Thinker Посмотреть сообщение
обработка бинарных деревьев чаше всего рекурсивна
Мне даже интересно стало, как вы будете обходить дерево, используя цикл
_liv_
211 / 211 / 80
Регистрация: 07.10.2015
Сообщений: 587
Завершенные тесты: 1
13.05.2017, 12:57     Что такое рекурсия? Зачем она нужна? #12
sancho1996, рекурсия используется для работы с данными, у которых структура (объект)
содержит вложенный объект, структурно аналогичный самому себе или (что бывает чаще) ссылку на такой же объект.
И тогда для работы с вложенным объектом просто вызываем самого себя, но с новыми параметрами.
Подобная структура объектов удобно тем, что так можно описать потенциально бесконечную структуру данных.
Подобные структуры используются при описании списков и графов, тех же деревьев.
Байт
Эксперт C
15634 / 9976 / 1499
Регистрация: 24.12.2010
Сообщений: 18,717
13.05.2017, 13:28     Что такое рекурсия? Зачем она нужна? #13
Цитата Сообщение от eXPonent Посмотреть сообщение
Подскажите нужна ли рекурсия в С++
ЕСЛИ её можно заменить for ?
В принципе, без рекурсии можно обойтись. Вот, Дональд Кнут в своей классической монографии "Искусство программирования" всячески рекурсии избегает. И для задач, в которых рекурсия просто напрашивается (не вычисление факториала! ) просто моделирует стеки. В итоге его алгоритмы выглядят на порядок более громоздкими, чем могли бы быть.

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

Не по теме:

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



А об рекурсии я имел ввиду, что она часто память жрут сильно много, даже грамотно написанные, а особенно если случайно допустил ошибку и она сожрет её всю
_liv_
211 / 211 / 80
Регистрация: 07.10.2015
Сообщений: 587
Завершенные тесты: 1
13.05.2017, 14:20     Что такое рекурсия? Зачем она нужна? #15
Цитата Сообщение от eXPonent Посмотреть сообщение
грамотно написанные
Грамотно написанные - грамотно используют память.
Кривые руки любую программу введут в ступор...
Любой метод - неуниверсален. К каждому типу задач необходимо пременять свой подход.
Рекурсия - не панацея, но порой без нее не обойтись, точнее, без нее намного сложнее...
Байт
Эксперт C
15634 / 9976 / 1499
Регистрация: 24.12.2010
Сообщений: 18,717
13.05.2017, 14:20     Что такое рекурсия? Зачем она нужна? #16
Цитата Сообщение от eXPonent Посмотреть сообщение
а особенно если случайно допустил ошибку и она сожрет её всю
Если допустил ошибку, то и без рекурсии будешь сожран.
eXPonent
48 / 48 / 2
Регистрация: 21.05.2012
Сообщений: 1,067
13.05.2017, 14:22     Что такое рекурсия? Зачем она нужна? #17
Цитата Сообщение от _liv_ Посмотреть сообщение
потенциально бесконечную структуру данных.
можно примеры?
как все данные должны быть конечными, иначе их вес будет бесконечным

Добавлено через 15 секунд
Цитата Сообщение от _liv_ Посмотреть сообщение
потенциально бесконечную структуру данных.
можно примеры?
как все данные должны быть конечными, иначе их вес будет бесконечным
S_el
2088 / 1595 / 305
Регистрация: 15.12.2013
Сообщений: 6,421
13.05.2017, 14:23     Что такое рекурсия? Зачем она нужна? #18
Цитата Сообщение от eXPonent Посмотреть сообщение
А об рекурсии я имел ввиду, что она часто память жрут сильно много, даже грамотно написанные, а особенно если случайно допустил ошибку и она сожрет её всю
В C++ компиляторы уже давно умеют в оптимизацию хвостовой рекурсии.
_liv_
211 / 211 / 80
Регистрация: 07.10.2015
Сообщений: 587
Завершенные тесты: 1
13.05.2017, 14:27     Что такое рекурсия? Зачем она нужна? #19
Цитата Сообщение от eXPonent Посмотреть сообщение
как все данные должны быть конечными, иначе их вес будет бесконечным
Я ж сказал "потенциально бесконечную", т.е. конечную, но сколько позволяет архитектура
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
13.05.2017, 16:58     Что такое рекурсия? Зачем она нужна?
Еще ссылки по теме:
C++ Что такое h -файл и obj-файл?Зачем они нужны?
Что такое "нейронная сеть" и как она работает? C++
Объясните, как работает sizeof() и зачем она в этой программе C++
зачем нужна перестановка C++
C++ Зачем нужна функция GetPrivateProfileString?

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

Или воспользуйтесь поиском по форуму:
kylroma
Одессит
196 / 67 / 19
Регистрация: 30.12.2013
Сообщений: 248
Записей в блоге: 1
Завершенные тесты: 1
13.05.2017, 16:58     Что такое рекурсия? Зачем она нужна? #20
Цитата Сообщение от eXPonent Посмотреть сообщение
Подскажите нужна ли рекурсия в С++
ЕСЛИ её можно заменить for ?
Макконелл советует обходиться без рекурсии, если это возможно. Код становится более понятным и меньше возможностей сделать ошибку, например переполнение стека.
Yandex
Объявления
13.05.2017, 16:58     Что такое рекурсия? Зачем она нужна?
Ответ Создать тему
Опции темы

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