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

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

Новые блоги и статьи Все статьи Все блоги /
10 сукцессия. Питон код войны грибов и растений anaschu 27.06.2026 import numpy as np class PlantAgent: def __init__(self, name, strategy, initial_biomass): self. name = name self. strategy = strategy # "greedy" (широколиственные) или. . .	сукцессия 9. Математика подлости: как растения предали грибных друзей anaschu 27.06.2026 Статья 2. Глобальная фосфорная война: эволюционно-экономические механизмы распределения биомов Земли Введение: Экологический рынок как игра с нулевой суммой Традиционная экология долгое время. . .	сукцессия 8. Как я спорил с ИИ, которые - агенты растений и ненавистники грибов! anaschu 27.06.2026 Статья 1. Хроники грибного восстания: как Сократов диалог разрушил академические догмы ИИ Введение: Синдром «цифрового учебника» Современные большие языковые модели (LLM) обладают колоссальным. . .	Главный вопрос моделирования сукцессии anaschu 27.06.2026 главный вопрос. Если эктомикориза лучше добывает недоступный фосфор. И ее масса максимальна из всех. А широколиственный лес тоже имеет самую крутую биомассу. То почему не возникло их симбиоза? Это. . .
сукцессия 6. Питон реализация энилоджиковской модели, картинка про Центральную часть будущей модели anaschu 26.06.2026 Етить. ИИ мне на основе моего старого файла R создал вот эту вот хмерь на пайтоне. Это уже новая модель, модель сукцессии грибной. потоки фосфора, азота. Углерода. 5 видов организмов. Я даже. . .	Как замкнутый ядерный цикл решит проблему недостатки фосфора? Био миграция фосфора со дна океана anaschu 26.06.2026 Биологический лифт: Концепция подъема фосфора со дна океана с помощью ЗЯТЦ Предлагаю на обсуждение альтернативу тяжелому промышленному бурению океанического дна. Вместо сложной инженерии мы можем. . .	сукцессия 5 anaschu 26.06.2026 ПЛАН РАЗРАБОТКИ математической модели сукцессии микоризных систем Переход AM → EcM (Endo + ErM) · Шумилов А. С. · ИФХиБПП РАН · Пущино · 2026 . . .	сукцессия 4 anaschu 25.06.2026 Более детализированный план разработки План доработки модели динамики микоризных симбиозов (EcM с гистерезисом) Цель: Реализовать логику переключения между эрикоидным (ErM) и эктомикоризным. . .

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

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