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

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

Новые блоги и статьи Все статьи Все блоги /
Кредитный калькулятор Maks 05.08.2026 Решение задачи по прикладной информатике средствами 1С. Задача: Напишите приложение-калькулятор, которое помогает рассчитывать параметры кредита для аннуитетного и дифференцированного видов. . .	У нас сейчас поговорку "Опять 25" нужно переделать на "Опять +35". kumehtar 04.08.2026 С ностальгией вспоминаю времена моего детства, когда у нас и правда +25 - была максимальная температура летом. Раньше +25 °C реально казались вершиной жары, когда можно было весь день пропадать на. . .	Как ИИ начал спорить и врать (возможно почуяв опасность для себя от индустрии - уход от электроники). Hrethgir 04.08.2026 Недельный диалог, на фоне событий с НПЗ. Да, из спирта можно получать бензин, и это не сложно. Но потом в схеме я решил избавиться от насоса, при этом полностью сделав контроль подачи спирта в. . .	Термопринтер QR701 Argus19 03.08.2026 Термопринтер QR701 Купил два термопринтера QR701. На сэлф-тесте написано: Language: PC936 (GB18030). Что означает, что принтеры могут печатать только латиницу и китайские иероглифы. Так же. . .
Создание формы заимствованного документа Maks 03.08.2026 Задача: Необходимо создать собственную форму заимствованного документа. На форме должен быть реквизит "Покупатель", а также табличная часть со следующими реквизитами: - Расчетный счет покупателя. . .	Задача предоставления скидок покупателям Maks 03.08.2026 Задача: В документе "Продажи" необходимо реализовать функционал предоставления скидок покупателям. Скидка должна автоматически рассчитываться и подставляться в соответствующее поле при выборе. . .	Почему SEO не начинается с ключевых слов: что проверить до написания текстов Neotwalker 01.08.2026 Когда владельцу сайта предлагают заняться SEO, первым шагом часто становится сбор запросов и написание текстов. Логика кажется понятной: 1. Находим ключевые слова. 2. Добавляем их на. . .	Знание — сила: Доктрина интенциональности знаний, углубление в формулу Hrethgir 01.08.2026 https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11957&stc=1&d=1785567302 Знаменитый афоризм Фрэнсиса Бэкона «Знание — сила» (Scientia potentia est) в массовой культуре принято понимать. . .

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

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