TL;DR

Всего рекурсивного кода может быть переведена в итеративно, однако некоторые из алгоритмов, которые являются, естественно, рекурсивные и более легко, представленных в этой форме.

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

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

Например,

, Чтобы ответить на вопросы, рассмотреть что-то немного более сложным. Извлечь то псевдо-код, чтобы пройти через деревья Википедии.

Рекурсивный Метод

postorder(node)
  if node == null then return
  postorder(node.left)
  postorder(node.right)
  visit(node)

Метод итерационный

iterativePostorder(node)
  parentStack = empty stack  
  lastnodevisited = null 
  while (not parentStack.isEmpty() or node ≠ null)
    if (node ≠ null)
      parentStack.push(node)
      node = node.left
    else
      peeknode = parentStack.peek()
      if (peeknode.right ≠ null and lastnodevisited ≠ peeknode.right) 
        node = peeknode.right
      else
        visit(peeknode)
        lastnodevisited = parentStack.pop() 

Ответы

1 в чем преимущество использования Рекурсивной Функции?

В вашем примере есть небольшое преимущество, но в которые я разместил выше, мы ясно видим, что рекурсивный метод:

• Выражена лучше, функциональности. Программирование, работать, делает все тяжелое этого этой возможности.
• Является более компактным. Меньше кода означает, обслуживание проще, меньше вероятность ошибок и т впереди.
• автоматическое Управление государства. В примере был использован итерационный клетки (stack). Думаю, теперь в языках, где управление памятью не является автоматическим. В C, например, вам придется добавить код, чтобы выделить и освободить элементов клетки в каждой итерации.

2 Как расположен потребление памяти?

Зависит от роли. Как правило, вы должны сделать анализ сложности памяти и времени для анализа различий, но это так очевидно, что в подавляющем большинстве случаев процедуры рекурсивные потребляют больше памяти и требуется больше циклов выполнения.

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

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

Кроме того, эффективность во многом зависит от количества запусков и уровень рекурсии. Так же, как и процедуры сортировки, некоторые экземпляры работают лучше, когда есть несколько итераций, и другие, когда есть более итераций. Некоторые реализации рекурсивные являются лучшими для обработки небольших. См., например, сайте , производительность Фибоначчи, где n <= 5 было лучше для рекурсивной версии.

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

С другой стороны, почти всегда рекурсивным процедурам, в конечном итоге, нуждающихся в быть переписаны в версии итеративный, когда число элементов или цифры, обработанных велик, в конце концов рекурсия имеет ограничение чувствительной столько памяти, сколько стека данных.

, И, кроме всего этого, существуют методы, которые могут повысить производительность и возможность выполнения рекурсивных, примеры этого:

• Memoization, или запоминания результатов
• Tail call, или рекурсия в шлейф

3 Я должен использовать рекурсивную функцию, а не Цикл, Повторяющийся часто (e.g. for/while)? Какие ситуации подходят для использования рекурсивной функции?

Следует, только если алгоритм является лучшим экспресс-рекурсивно и если использование этого алгоритма в целом не будет превышать ограничения рекурсии.

Я Считаю, что идеальных условиях были примере выше, а именно: (

• Алгоритмы по своей сути рекурсивные, лучше выражены в этом формате
• Использованием вычислительной умеренный, чтобы не превышать ограничения рекурсии

1. рекурсивные Функции являются преимуществом в случаях, когда проблема есть, конечно, определенная функция себе, а в том, что рекурсивные решения будет проще. В начале это может показаться странным, поскольку рекурсия кажется сложным и запутанным, но со временем и с пониманием (много практики) вы научитесь выявлять проблемы в том, что она является лучшим решением.
2. рекурсия, как Правило, представляет собой накладные расходы памяти, это происходит потому, что каждый вызов функция выделяет кадр Стека вызовов, так что каждый новый вызов, что рекурсивная функция делает сама выделяет новый кадр в стеке, и каждый новый кадр, накапливается память, вся эта память только libereda, когда все chamdas рекурсивные достигают точки остановки (когда $num == 0 в вашем примере). В случае, если функции рекурсивные вызовы слишком много себе (набирайте "кадры" тоже в клетке) будет происходить "Stack Overflow" (переполнение стека). Рекомендую прочитайте этот вопрос и ответы если вы хотите больше понять о том, что в стеке вызовов, и, как переполнение стека может произойти.
3. Как жизнь сложна ответ, это зависит. Как я уже говорил ранее преимущество рекурсии проблем, равен по своей природе, и для которых решение рекурсивной это самый простой и прямой, классический пример-это обработка Деревьев бинарные, структуры данных по своей сути рекурсивной. Мой последнее предположение: узнайте, как рекурсия, понять, как работает, практиковать, в конце концов вы будете знать, что лучшее время для использования.

, Кто не испытывает на практике оказывается не понимая теории. Так что это всегда хорошо, показать практический пример использования в "реальном мире".

Основной намек, чтобы знать, когда развертывание, когда необходимо выполнить несколько петель повторения числа.

, Если вы уверены, что можете решать что-то с Х-число циклов повторения, то логично, что наиболее разумным является применение нескольких связей, при условии, что не будут много. Например, 10 петель-это много тогда было бы дело, если подумать использования рекурсии.

Представьте

while(){
    while(){
        while(){
            while(){
                while(){
                    while(){
                        while(){
                            while(){
                                while(){
                                    while(){

, Как это будет выглядеть в рекурсии?

function foo()
    while(){
       foo();

Ниже приведен пример практического использования.

В Этой ситуации мне пришлось создать функцию для нормализации path (filesystem). В PHP есть функция realpath() однако, эта функция нормализуется только один существующий путь. Функция ниже делает то же самое, что realpath() с той лишь разницей, что игнорирует, если путь существует, или нет. Целью является только нормализовать.

Это практический пример использования рекурсии. Здесь, в этом случае не будет использовать несколько связей вручную.

$path_canonicalize = function($str, $started = false) use(&$path_canonicalize)
{
    $str = str_replace('/', DIRECTORY_SEPARATOR, $str).DIRECTORY_SEPARATOR;

    if (!$started)
        $str = preg_replace("/".preg_quote(DIRECTORY_SEPARATOR, "'".DIRECTORY_SEPARATOR."'")."{2,}/", DIRECTORY_SEPARATOR, $str);

    $pos = strpos($str, '..'.DIRECTORY_SEPARATOR);
    if ($pos !== false)
    {
        $part = trim(substr($str, 0, $pos), DIRECTORY_SEPARATOR);
        $str = $path_canonicalize(trim(substr($part, 0, strrpos($part, DIRECTORY_SEPARATOR)), DIRECTORY_SEPARATOR).DIRECTORY_SEPARATOR.trim(substr($str, $pos+3), DIRECTORY_SEPARATOR), true);
    }
    return rtrim($str, DIRECTORY_SEPARATOR);
};

/*
Try those cases to check the consistency:
$str = __DIR__.'/template//////../header//..';
$str = __DIR__.'/template///..///../header//..';
$str = __DIR__.'/template/../header/..';
$str = __DIR__.'/template/../header/../';
$str = __DIR__.'/template/../header/..//';
$str = __DIR__.'/template/../header/..///';
$str = __DIR__.'/template/../header/..///..';
$str = __DIR__.'/template/../header/..///../';
$str = __DIR__.'/template\\..\\header\\..';
*/
$str = __DIR__.'/template/../header/..///..//';
echo 'original: '.$str.PHP_EOL;
echo 'normalized: '.$path_canonicalize($str).PHP_EOL;

Кроме того, что было сказано в других ответах, рекурсивные функции будут особенно выгодно в тех случаях, где это возможно, разделить проблему на половину. Это становится очевидным при работе с двоичных деревьев, но не ограничивается этим.

И Рассмотрим две функции ниже, чтобы рассчитать умножения с последующих сумм. В то время как решение итеративный имеет сложность O(n), рекурсивное решение имеет сложность O(log(n)). Это должно компенсировать накладные расходы для вызова метод.

Извините за код на Python, был язык, что я уже работаю, но я думаю, что вам понятно выражать понятие. Если у вас есть время спустя, я могу попробовать перевести тебя на PHP.

def multIterativa(a, b):
    total = 0
    for i in range(b):
        total += a
    return total

def multRecursiva(a, b):    
    if b == 0:
        return 0
    if b == 1:
        return a
    total = multRecursiva(a, int(b / 2))
    total += total
    if b % 2 != 0:
        total += a
    return total