Ваше отношение к рекурсии?

Question

[nepster-web]

Где-то примерно еще лет 5 назад у меня сложилось сомнительное мнение в отношении рекурсий.
Однако последнее время в них возникает некоторая необходимость.

Например если у вас есть ар-объект с множеством реляций в 3 или 4 вложенности и есть задача обернуть это все дело в коллекций. Тоесть каждую запись вложенных реляций обернуть в коллекции.

Тут весьма сильно напрашивается рекурсия. Будет ли тут оправдано ее использование и вообще есть ли смысл их использовать или все-же избегать?

Comments

[Сергей Кузьмин]

Пользователь: Факториал без рекурсии решается очень просто. https://ru.wikibooks.org/wiki/%D0%A0%D0%B5%D0%B0%D... А вот обход дерева - да. Там трудно без факториала обойтись.

[Artem Gapchenko]

Пользователь угу, вот только рекурсивное решение факториала на языке, не умеющем в хвостовую рекурсию, быстро обернётся ошибкой переполнения стека.

[Artem Gapchenko]

Пардон, имел в виду "не умеющем в оптимизацию хвостовой рекурсии".

[Дмитрий Беляев]

Пользователь:

uint factorial(uint n) {
  uint r = 1;
  if(n < 2) return 1; // так как факториал 0 и 1 есть 1
  for(uint i = 2; i <= n; i++) r *= i;
  return r;
}

[Даниил Демидко]

Дмитрий Беляев:

// Как не крути, а рекурсия красивее
int factorial(const int&number) { 
    return number ? number * GetFactorial(number - 1) : 1; 
}

[Даниил Демидко]

Как не крути, а рекурсия красивее

int factorial(int n) { return n ? n * factorial(n - 1) : 1; }

[nepster-web]

Даниил Демидко: java ? что-то не люблю сокращенный синтаксис =). Там была метка, ее удалили, вопрос скорее адресован к пхп. У меня там сложилось, что с детства избегаю рекурсии. Если дерево, то Nested Set и тп. В крайнем случае рекурсия + кеш, а тут вопрос именно реалтайм выполнения.

[Даниил Демидко]

nepster09: У меня плюсы) Просто привык что компилятор оптимизирует хвостовую рекурсию. Насчет php конечно не знаю)

[nepster-web]

Даниил Демидко: =) я программирую на С используя шаблонизатор php =)

Answer 1

[Saboteur]

Рекурсия - это отличное решение для отдельных задач. Такое же, как использование case вместо if, или использование sql вместо массивов данных.

Просто используйте их там, где рекурсия работает лучше других решений и все. Есть множество задач, где рекурсия будет best practice.

Чтоже касается того, что "в каких-то языках это плохо работает", так пока не попробуете - не узнаете.

Answer 2

[Oleg]

Рекурсия - так же как и любой другой инструмент - это в первую очередь инструмент.

Её можно и нужно использовать там где её нужно и можно использовать :)

Есть многие задачи которые сложно решить без рекурсии, и в конце получиться что фактически вы реализуете рекурсию просто без вызова функции, фактически же рекурсия остаётся, просто менее ярко выраженная.

Если же можно реализовать без рекурсии задачу - то обычно лучше реализовывать без неё.

Answer 3

[Даниил Демидко]

Рекурсия медленная - но хвостовую, gcc оптимизирует, итерациями заменяя.
Но она все равно медленнее циклов будет, проверить сие можно числа Фибоначчи исчисляя.
Впрочем люблю я ее больше нежели итерации ибо выглядит красивее она и сие есть факт.
Рекурсия, равно как и итерации, хороша в меру. Зная дао мы можем использовать и то и другое, ничем не управляя.
Рекомендую к прочтению "Дао дэ цзин", Лао Цзы. Книга ответит на многие вопросы касательно использования патернов ООП в своем проекте, рекурсии и много другого. В общем маст хэв каждого C++ программиста.

Answer 4

[abcd0x00]

При рекурсии создаются копии одних и тех же переменных многократно - жрётся память и время. Как бы там ни было, она имеет и максимальную глубину ещё - то есть при очень длинной обработке программа выпадет, потому что не хватит ресурсов системы для рекурсии. Так что память, время и граница - это то, чего нет в аналогичном цикле.

Answer 5

[GavriKos]

Ваше отношение к морозильнику? Где то примерно лет 5 назад сложилось сомнительное мнение, однако сейчас все чаще покупаю пельмени и их надо где то хранить.

Короче, вопрос бредовый. Если рекурсия вам упростит решение задачи - используйте ее смело.

Comments

[nepster-web]

Не знаю как бредовое, но например ходили слухи. что некоторые языки программирования весьма плохо переваривают рекурсии. Когда-то натыкался на статью про node.js, что там обычным выражением с не очень большой глубиной ложили скрипт секунд на 10. Было что-то такое:

recursiveFunction1() + recursiveFunction2()

Не помню, но вроде в каждой до 100 итераций.

[GavriKos]

nepster09 Положить скрипт можно и без рекурсии.

[nepster-web]

GavriKos: это понятно. У меня скорее всего есть беспокойство на счет скорости работы. например не сильно ли 10 - 100 итераций рекурсии замедлит выполнения скрипта? А что если 100 - 1000 ?

[GavriKos]

nepster09 Вы технически понимаете что такое рекурсия? Это просто вызов методов. Больше всего скорость зависит от того, что вы делаете в каждой итерации. В какой то степени это может зависеть от работы коллстека интерпретатора/языка, но я сомневаюсь что есть какие то проблемы с этим в современных языках.

[Дмитрий С]

nepster09: Вы занимаетесь преждевременной оптимизацией

Answer 6

[protven]

У меня отношение к рекурсии точно такое же как к рекурсии.

Comments

[Дмитрий С]

А какое у Вас отношение к рекурсии?:D

[DevMan]

Дмитрий С: ну написано же "точно такое же"

[Дмитрий С]

DevMan: "точно такое же" как к рекурсии - а какое к рекурсии?

[DevMan]

Дмитрий С: как к рекурсии, очевидно же.

[Дмитрий С]

DevMan: а какое к рекурсии? Предлагаю завершить погружение :D

Answer 7

[Roman K]

Рекурсия - это красивое зло. Лучше избегать, но иногда можно.