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

@sancho1996 · Регистрация: 24.06.2013

Студворк — интернет-сервис помощи студентам

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

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

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

@Second · 02.07.2013, 20:00

Это одно из многих определений в учебниках, которое крайне редко используется на практике.
В педевикии лаконично описано, но маловероятно повстречать сие в реалиях.

@Thinker · 02.07.2013, 20:04

Сообщение от Second

маловероятно повстречать сие в реалиях.

да ну... та же широко используемая сортировка quicksort рекурсивная. обработка бинарных деревьев чаше всего рекурсивна и многое другое.

@sancho1996 · 02.07.2013, 20:10 **[ТС]**

Сообщение от Thinker

да ну... та же широко используемая сортировка quicksort рекурсивная. обработка бинарных деревьев чаше всего рекурсивна и многое другое.

расскажите о рекурсии по подробнее пож

@nexen · 02.07.2013, 20:16

sancho1996, это просто вызов функции самой себя. Допустим:

C++
1
2
3
4
5
6
bool f(int x)
{
if (x == 1) return false;
else
f(x - 1);
}

Функция будет вызывать себя -ндцать раз, до тех пор пока не вызовет с числом, равным 1, а затем вызов прекратится.

@castaway · 02.07.2013, 20:40

Много лишнего для примера..

C++
1
2
3
4
5
void func( int n )
{
    if ( !n ) return; // если n == 0 ...
    func( n - 1 );
}

Собственно, она ничего не делает, просто пример работы рекурсии.

@Thinker · 02.07.2013, 20:45

Сообщение от lazybiz

она ничего не делает, просто пример работы рекурсии.

вот откуда потом появляются фразы типа

Сообщение от Second

Это одно из многих определений в учебниках, которое крайне редко используется на практике... маловероятно повстречать сие в реалиях.

@castaway · 02.07.2013, 20:52

Не по теме:

Thinker, ))))))

@eXPonent · 13.05.2017, 09:18

Сообщение от Thinker

да ну... та же широко используемая сортировка quicksort рекурсивная. обработка бинарных деревьев чаше всего рекурсивна и многое другое.

Подскажите нужна ли рекурсия в С++
ЕСЛИ её можно заменить for ?

@dailydose · 13.05.2017, 11:29

Сообщение от eXPonent

Подскажите нужна ли рекурсия в С++
ЕСЛИ её можно заменить for ?

очевидно же что нет, ибо stack overflow!

Рыжий Лис · 13.05.2017, 11:47

Сообщение от eXPonent

ЕСЛИ её можно заменить for ?

Сообщение от Thinker

обработка бинарных деревьев чаше всего рекурсивна

Мне даже интересно стало, как вы будете обходить дерево, используя цикл

@liv · 13.05.2017, 12:57

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

Байт · 13.05.2017, 13:28

Сообщение от eXPonent

Подскажите нужна ли рекурсия в С++
ЕСЛИ её можно заменить for ?

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

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

Добавлено через 3 минуты
Ну, а класс задач, в которых применение рекурсии естественно, кратко описал уважаемый _liv_.
А вообще-то и без циклов for можно обойтись, и вообще без циклов. Есть же goto

@eXPonent · 13.05.2017, 14:14

Не по теме:

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

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

@liv · 13.05.2017, 14:20

Сообщение от eXPonent

грамотно написанные

Грамотно написанные - грамотно используют память.
Кривые руки любую программу введут в ступор...
Любой метод - неуниверсален. К каждому типу задач необходимо пременять свой подход.
Рекурсия - не панацея, но порой без нее не обойтись, точнее, без нее намного сложнее...

Байт · 13.05.2017, 14:20

Сообщение от eXPonent

а особенно если случайно допустил ошибку и она сожрет её всю

Если допустил ошибку, то и без рекурсии будешь сожран.

@eXPonent · 13.05.2017, 14:22

Сообщение от _liv_

потенциально бесконечную структуру данных.

можно примеры?
как все данные должны быть конечными, иначе их вес будет бесконечным

Добавлено через 15 секунд

Сообщение от _liv_

потенциально бесконечную структуру данных.

можно примеры?
как все данные должны быть конечными, иначе их вес будет бесконечным

@S_el · 13.05.2017, 14:23

Сообщение от eXPonent

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

В C++ компиляторы уже давно умеют в оптимизацию хвостовой рекурсии.

@liv · 13.05.2017, 14:27

Сообщение от eXPonent

как все данные должны быть конечными, иначе их вес будет бесконечным

Я ж сказал "потенциально бесконечную", т.е. конечную, но сколько позволяет архитектура

@kylroma · 13.05.2017, 16:58

Сообщение от eXPonent

Подскажите нужна ли рекурсия в С++
ЕСЛИ её можно заменить for ?

Макконелл советует обходиться без рекурсии, если это возможно. Код становится более понятным и меньше возможностей сделать ошибку, например переполнение стека.

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .	SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .	SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm 8Observer8 30.01.2026 Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .	SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .	Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .	SDL3 для Android: Загрузка PNG с альфа-каналом с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 28.01.2026 Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .

@sancho1996 0 / 0 / 0 Регистрация: 24.06.2013 Сообщений: 55

	Что такое рекурсия? Зачем она нужна? 02.07.2013, 19:52. Показов 16689. Ответов 41 Метки нет (Все метки) Объясните пож человеческим языком, что такое Рекурсия. Я знаю что это вызов функции самой себя. Но всё равно не могу догнать зачем она нужна. Заранее спасибо! 0

@Second 118 / 80 / 1 Регистрация: 10.08.2011 Сообщений: 664
	02.07.2013, 20:00
	Это одно из многих определений в учебниках, которое крайне редко используется на практике. В педевикии лаконично описано, но маловероятно повстречать сие в реалиях. 0

@castaway
	02.07.2013, 20:52
	Не по теме: Thinker, )))))) 0

@liv 5120 / 4574 / 855 Регистрация: 07.10.2015 Сообщений: 9,462
	13.05.2017, 12:57
	sancho1996, рекурсия используется для работы с данными, у которых структура (объект) содержит вложенный объект, структурно аналогичный самому себе или (что бывает чаще) ссылку на такой же объект. И тогда для работы с вложенным объектом просто вызываем самого себя, но с новыми параметрами. Подобная структура объектов удобно тем, что так можно описать потенциально бесконечную структуру данных. Подобные структуры используются при описании списков и графов, тех же деревьев. 1

@eXPonent 99 / 52 / 27 Регистрация: 21.05.2012 Сообщений: 1,170
	13.05.2017, 14:14
	Не по теме: согласен в ассемблере без джампа никак) он по всюду А об рекурсии я имел ввиду, что она часто память жрут сильно много, даже грамотно написанные, а особенно если случайно допустил ошибку и она сожрет её всю 0