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

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

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

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

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

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

@liv · 13.05.2017, 17:15

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

Код становится более понятным

спорное утверждение...
Обход дерева при помощи рекурсии выглядит элегантно и понятно, в отличие от цикла.
Для каждой задачи свои методы. А ошибки... Они в прямой зависимости от кривизны рук...

@kylroma · 13.05.2017, 17:19

_liv_, ну он не скрывает, что его советы спорные и могут противоречить друг-другу.

@liv · 13.05.2017, 17:29

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

его советы спорные и могут противоречить друг-другу

Ну и зачем тогда предлагать здесь спорные советы?

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

@Ferrari F1 · 13.05.2017, 18:01

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

Что такое рекурсия?

вызов программы самой себя

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

Зачем она нужна?

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

@eXPonent · 13.05.2017, 18:15

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

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

примеры можно, а то я не понимаю о чем вы говорите.

Добавлено через 4 минуты

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

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

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

можно примеры?

@liv · 13.05.2017, 18:28

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

можно примеры?

Навскидку, например, организовать индексы по некой огромной базе данных в виде двоичного дерева. Хранить в файле. А работать с ним, отображая его в память. Поиск по такому дереву будет практически мгновенным. Размер ограничен только размером диска.
Удобно тем, что коррекция происходит быстро и практически не зависит от объема информации

Байт · 13.05.2017, 18:55

Не по теме:

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

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

Как говорил Веничка Ерофеев - "Плюньте ему в его соленые рыжики!:D

Добавлено через 17 минут
Итак.
1.Без рекурсии обойтись можно. Есть циклы и, в конце концов, ГОУТО
2.Для реализации существенно рекурсивных алгоритмов нужен стек. Его можно и самостоятельно смоделировать. Но зачем, если язык уже предлагает готовое?
Использование этого готового стека упрощает ваш код, но вы теряете прямой контроль за его поведением. За переполнением, например. Контроль косвенный возможен, но его применение весьма непросто, средо/аппаратно зависимо и может усложнить код настолько, что моделируемый стек покажется конфеткой.
3. Как говаривал К.Прутков, "Даже не пытайтесь объять необъятное". Ваш компьютер (вместе со всеми сетями мира) - всего лишь конечный автомат. И совершенно нелепо решать на нем истинно бесконечные задачи. Ограничения есть всегда.
В качестве упражнения попробуйте написать программу, выводящую все десятичные знаки корня из двух.

@Renji · 13.05.2017, 19:02

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

примеры можно, а то я не понимаю о чем вы говорите.

Хвостовая рекурсия - рекурсивный вызов строго в конце функции. Точнее, вызов сразу перед return. Во многих случаях такой вызов можно заменить тупым goto в начало функции и не транжирить стек. Хотя, можно придумать особо изощренный пример в котором фокус не сработает.

Сообщение от Байт

2.Для реализации существенно рекурсивных алгоритмов нужен стек. Его можно и самостоятельно смоделировать. Но зачем, если язык уже предлагает готовое?

Штатный стек не резиновый, на рекурсивном алгоритме заливки изображения 4096x4096 сломаться может.

@liv · 13.05.2017, 19:10

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

Штатный стек <...> сломаться может

Так для стека можно дополнительную память запросить.
И вообще, о чем мы тут говорим? Пред написанием программы надо сначала все продумать. И принять тот метод решения, который приемлем. Нет универсальных методов. Все имеет свои ограничения.

Байт · 13.05.2017, 19:36

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

Штатный стек не резиновый,

У меня такое ощущение, что ниже процитированных слов вы просто не посмотрели.

@eXPonent · 14.05.2017, 12:47

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

Хвостовая рекурсия - рекурсивный вызов строго в конце функции. Точнее, вызов сразу перед return. Во многих случаях такой вызов можно заменить тупым goto в начало функции и не транжирить стек. Хотя, можно придумать особо изощренный пример в котором фокус не сработает.

никогда об этом бы не подумал
но ведь как раз в том случае можно все написать через for внутри функции

@_Ivana · 14.05.2017, 15:59

В случае хвостовой рекурсии - да. В случае хвостового вызова - нет.

@eXPonent · 14.05.2017, 18:00

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

В случае хвостовой рекурсии - да. В случае хвостового вызова - нет.

а можно примеры, вашего варианта, а то трудно ориентироваться в этих понятиях
или это уже зарезервированные вещи в языке С++ ?

@Renji · 14.05.2017, 18:10

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

а можно примеры, вашего варианта, а то трудно ориентироваться в этих понятиях

Там везде суть одна. Наивная реализация:
Вызвать что-то там.
Выкинуть из стека данные текущей функции.
return.

Оптимизация 1:
Выкинуть из стека данные текущей функции (их все равно больше никто не использует, ведь дальше return).
Вызвать что-то там.
return.

Оптимизация 2:
Выкинуть из стека данные текущей функции (их все равно больше никто не использует, ведь дальше return).
goto что-то там (из-за особенностей аппаратной реализации вызова функций, эквивалентно паре call/ret идущей строго друг за другом).

@_Ivana · 14.05.2017, 18:10

C++
1
2
3
bool isOdd(int);
bool isEven(int n) { return n==0 ? true : isOdd(n-1); }
bool isOdd(int n) { return n==0 ? false : isEven(n-1); }

@_stanislav · 14.05.2017, 19:14

sancho1996,

Assembler
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
; Рекурсивная процедура вычисления факториала
; вход: CX - число без знака
; выход: AX - результат
factorial:
    push bp                 ;Сохранение BP
    mov bp,sp               ;BP=SP
    mov ax,[bp+4]           ;AX=параметр
    test ax,ax              ;Проверка AX
    jz f_ret1               ;Если 0, вернуть 1
    dec ax                  ;Декремент AX
    push ax                 ;Помещение параметра в стек
    call factorial          ;Вызов процедуры для предыдущего числа
    mul word[bp+4]          ;Умножение результата на параметр процедуры
    jmp f_ret               ;Переход к возврату из процедуры
f_ret1:
    inc ax
f_ret:
    pop bp                  ;Восстановление BP
    ret 2                   ;Возврат из процедуры

в этом коде рекурсия более наглядна.

ValeryS · 14.05.2017, 19:15

Сообщение от Байт

в которых рекурсия просто напрашивается (не вычисление факториала!

как я уже говорил, зависит от определения факториала
если так, факториал есть произведение всех натуральных чисел от 1 до n, это цикл
а если, факториал есть произведение n на факториал n-1, факториал 1 равен 1, то это рекурсия

Байт · 14.05.2017, 19:22

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

зависит от определения факториала

Так для того нам и дана верхняя оконечность, чтобы понять, что эти определения равносильны, и применить наиболее простую и естественную реализацию

@_Ivana · 14.05.2017, 19:26

Байт, в случае факториала и фибоначчей это тривиально. Но могу накидать других случаев, когда итеративная реализация неочевидна, а рекурсивная - более чем.

Байт · 14.05.2017, 19:31

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

Но могу накидать других случаев,

Не надо! Не кидай! Побереги бисер!
Я и так тебе верю!

Добавлено через 53 секунды
ЗЫ. Смотри в этой теме мой пост про Кнута.

Новые блоги и статьи Все статьи Все блоги /
Книги по геймдизайну, левел-дизайну, игровым механикам и проектированию игрового опыта 8Observer8 08.11.2026 Содержание блога \| English Version 1. 2003 - 06 - Designing Virtual Worlds (1st Edition) Автор: Richard A. Bartle \| Объем: 768 стр. Ссылки: Amazon . . .	Родители токсичные абьюзеры по отношению к своим детям ругают их оскорбляют не любят zorxor 08.11.2026 Жить в атмосфере постоянных оскорблений, критики и холодности со стороны родителей — это тяжелое и болезненное испытание, которое оставляет глубокие эмоциональные раны. Токсичное и абьюзивное. . .	Как только я захожу к себе в свою комнату я сразу же с себя снимаю свои трусы. Ответ от Джемени ИИ. zorxor 08.11.2026 Джемени, как только я захожу к себе в свою комнату я сразу же с себя снимаю свои трусы. Многие люди, возвращаясь домой, сразу переодеваются в максимально свободную одежду или вовсе предпочитают. . .	Паттерн очереди действий/команд (Action / Command Queue). Система очереди действий и кат-сцен с SDL3 Callbacks, cglm и OpenGL 8Observer8 07.11.2026 Содержание блога \| English Version Руководство для начинающих по реализации паттерна очереди действий/ команд (Action / Command Queue) на C++ (C++20) с использованием официального SDL3 Callbacks. . .
Проверка полного ФИО в типовом справочнике Maks 07.11.2026 Решение реализовано в конфигурации КА2, на примере справочника "КонтактныеЛицаПартнеров". Задача: Запрет инициалов. Не допускаеть использование сокращений вида "И. И. ", "И. И. ", "И И" и. . .	Про "Windows must die!" kumehtar 04.11.2026 Знаете, чет накатило. . . . Когда-то это было почти боевым кличем: мол, нормальный человек сидит на DOS, OS/ 2 или Linux, а вот это вот - Must Die. А теперь человек произносит «мастдай» с усмешкой - и. . .	Красочные поля с номером страницы svg+background-image russiannick 04.11.2026 Красочные поля с номером страницы не менее важны чем в эпоху бумажных книг. Посему спешу представить почтеннейшей публике этот важный инструмент который эти поля и формирует. В процессе разработки. . .	Вступаем в новую фазу генерации favicons, векторную. russiannick 02.11.2026 Теперь нет нужды скрывать что используется простой svg. Исходный код изображения помещаем в поле и жмем кнопку. Исходник преобразуется в вид корректный для помещения в favicon или в url(). Нажатие. . .

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

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

@kylroma Одессит 243 / 88 / 44 Регистрация: 30.12.2013 Сообщений: 316 Записей в блоге: 2
	13.05.2017, 17:19
	_liv_, ну он не скрывает, что его советы спорные и могут противоречить друг-другу. 0

@_Ivana 4949 / 2289 / 287 Регистрация: 01.03.2013 Сообщений: 5,991 Записей в блоге: 32
	14.05.2017, 15:59
	В случае хвостовой рекурсии - да. В случае хвостового вызова - нет. 0

@_Ivana 4949 / 2289 / 287 Регистрация: 01.03.2013 Сообщений: 5,991 Записей в блоге: 32
	14.05.2017, 19:26
	Байт, в случае факториала и фибоначчей это тривиально. Но могу накидать других случаев, когда итеративная реализация неочевидна, а рекурсивная - более чем. 0