Считается ли рекурсия устаревшим методом обхода по сравнению с использованием стека?

Question

Я читал в нескольких местах, где люди предпочитают использовать стек вместо рекурсии. Это потому, что рекурсия рассматривается как устаревший способ выполнить работу или оба метода одинаково применимы в разных контекстах?

Answer 1

Нет. Как раз наоборот. Рекурсия - это естественный способ выразить целый класс проблем. Стек - это способ симулировать это, если у вас нет рекурсии.

См., Например, этот вопрос . Или рассмотрим стандартную рекурсивную функцию: вычисление n -го числа Фибоначчи.

Вы помните, что числа Фибоначчи являются сериями

0,1,1,2,3,5,8,13, ...

определено так, что F _n = F _n-1 + F _n-2 .

Это может быть записано как рекурсивное определение как

Базовый корпус:
F (0) = 0
F (1) = 1
Рекурсивный шаг:
F (n) = F (n-1) + F (n-2)

Итак, у вас есть F (0) = 0, F (1) = 1, F (2) = F (0) + F (1) = 1 и т. Д.

Простая программа для вычисления этого (в C только для ухмылки):

int fib(int n) {
    /* we'll ignore possible negative arguments, see Wikipedia */
    switch(n) {
       case 0: return 0; break;
       case 1: return 1; break;
       default: return fib(n-1)+fib(n-2); break;
    }
}

Обратите внимание, насколько близко эта программа соответствует исходному определению?

Дело в том, что C управляет всеми промежуточными результатами в стеке вызовов . Некоторые языки не определены для этого (единственный, что я могу придумать, это старый Фортран, но я уверен, что есть и другие). Если вы пишете на ассемблере или старом FORTRAN, то вам нужно управлять своим собственным стеком, чтобы отслеживать эти промежуточные результаты.

Answer 2

Итерация часто быстрее / имеет меньше накладных расходов, чем рекурсия. С помощью рекурсии мы неявно используем стек машины в качестве нашего стека - мы получаем это «бесплатно» - но мы оплачиваем стоимость дорогостоящих вызовов функций (и сопутствующего управления стеками машин).

Но рекурсивные функции часто более интуитивно понятны для написания и чтения.

Часто можно написать функцию с использованием рекурсии, оставить ее до тех пор, пока она не станет узким местом, а затем заменить ее итеративной функцией, использующей явный стек.

Answer 3

Обновлено , чтобы включить исправление рыбьих губ.

Использование стека является стандартной техникой устранения рекурсии

См. Также: Что такое хвостовая рекурсия?

Пример Tail-Recursion (который можно удалить с помощью итерации):

public class TailTest
{   
    public static void Main()
    {       
        TailTest f = new TailTest();
        f.DoTail(0);
    }

    public void DoTail(int n)
    {       
        int v = n + 1;      
        System.Console.WriteLine(v);    

        DoTail(v);   // Tail-Recursive call
    }
}

Answer 4

Если вы находитесь в языке программирования / среде, где хвостовые вызовы увеличивают стек (не применяется оптимизация хвостовых вызовов (TCO)), тогда лучше избегать глубокой рекурсии, и предпочтительными являются итеративные решения, которые могут использовать структуру данных стека .

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

(Это немного слишком широко, но в целом я бы ни в коем случае не назвал рекурсию "устаревшей".)

Answer 5

Нет-нет, я думаю, что современные разработчики должны подчеркнуть удобочитаемость и простоту обслуживания в течение нескольких миллисекунд.

Если проблема рекурсивная, я полностью рекомендую ваше решение БЫТЬ рекурсивной.

Кроме того, вы можете в конечном итоге ввести некоторые непредвиденные ошибки, пытающиеся заставить итеративное / составное решение.