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

@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 секунды
ЗЫ. Смотри в этой теме мой пост про Кнута.

Новые блоги и статьи Все статьи Все блоги /
Море в объективе kumehtar 06.07.2026 Хотел написать много проникновенных слов, но передумал. Оно само - говорит. Кто слышит тот слышит.	Оказывается, Unreal Engine позволяет качество на порядки выше, чем было в Lineedge Etyuhibosecyu 05.07.2026 Жаль, конечно, что я не узнал об этом, пока Lineedge существовала, а то бы Noname2331 написал, что волки превращаются в пиксельную кашу, а я бы его попросил скачать какую-нибудь бриллиантовую или Pro. . .	Doom для терминала без стрельбы и монстров. 3D Raycasting на ascii. dcc0 05.07.2026 Попросил нейронную сеть deepai. org написать рейкастинг 3D с библиотекой ncurses для Linux. Чтобы можно было ходить на стрелочки. Чтобы стены были отрисованы символами. Справилась. Первый вариант. . .	Установка статуса документа по условию Maks 05.07.2026 Алгоритм из решения ниже реализован на нетиповом документе "НарядПутевка" разработанного в КА2. Задача: в табличной части "Материалы" документа при записи автоматически устанавливать статус. . .
Сезонность и суточность закисления почв anaschu 04.07.2026 200 часов это все равно моловато. Есть ситуации, но нестандартные, когда смена происходит за 5 лет. Но обычно это 50 лет и более. Наверное, закисление почвы происходит сезонно в средней. . .	В чем ценность человеческого опыта в глобальном смысле? kumehtar 03.07.2026 Возможно, ценность человека не в том, что он однажды достигает мудрости, а в том, что он становится носителем карты пути. Он знает не только истину, но и последовательность внутренних изменений,. . .	интеграция AnyLogic с самописным REST API и переход на Odoo anaschu 03.07.2026 Успешная интеграция AnyLogic с самописным REST API и переход на промышленную Odoo WMS Сегодня проделал огромный путь от простой симуляции физических процессов до построения полноценной. . .	Поиск всех путей на ориентированном графе. Linux dcc0 02.07.2026 Переработка старого кода из моей статьи. Через несколько переработок от PHP кода к C89 (надеюсь, 89). Но довольно запутанно получилось. Код для Linux. Но если убрать time и то, что с ним. . .

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

	Что такое рекурсия? Зачем она нужна? 02.07.2013, 19:52. Показов 17111. Ответов 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