Рекурсия в схеме и стек вызовов

Я учусь в университете, изучаю Racket/Scheme и C в качестве вводных курсов для получения степени CS.

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

Теперь в функциональном языке, таком как Scheme, рекурсия используется постоянно. Я знаю, что хвостовая рекурсия является огромным преимуществом в Scheme, и, насколько я понимаю, для нее требуется только один кадр стека (может ли кто-нибудь прояснить это?), независимо от того, насколько глубока рекурсия.

Мой вопрос: как насчет рекурсии без хвоста? Сохраняется ли каждое функциональное приложение в стеке вызовов? Если бы я мог получить краткий обзор того, как это работает, или указать мне ресурс, я был бы признателен; Кажется, я не могу найти нигде, где бы прямо говорилось об этом.


stack recursion callstack scheme tail-recursion
person Anthony Calandra    schedule 24.01.2014    source источник

Ответы (2)


arrow_upward
3
arrow_downward

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

На мгновение давайте предположим, что javascript поддерживает оптимизацию хвостовых вызовов, второе из этих определений функций будет использовать только 1 кадр стека, а первое из-за + потребует дополнительного кадра стека.

function sum(n) {
   if (n === 0)
      return n;
   return n + sum(n - 1);
}

function sum(n) {
  function doSum(total, n) {
    if (n === 0)
       return total;
    return doSum(total + n, n - 1);
  }
  return doSum(0, n);
}

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

Концептуально вызовы для первого определения выглядят так

3 + sum(2)
3 + sum(2) = 3 + 2 + sum(1)
3 + sum(2) = 3 + 2 + sum(1) = 3 + 2 + 1 + sum(0)
3 + sum(2) = 3 + 2 + sum(1) = 3 + 2 + 1 + sum(0) = 3 + 2 + 1 + 0
3 + sum(2) = 3 + 2 + sum(1) = 3 + 2 + 1 + sum(0) = 6
3 + sum(2) = 3 + 2 + sum(1) = 6
3 + sum(2) = 6
6

вызовы для второго определения выглядят так

sum(3, sum(2)) = sum(5, sum(1)) = sum(6, sum(0)) = 6
person Bhaskar    schedule 24.01.2014
comment
Когда вы говорите: в то время как для первого из-за + потребуется дополнительный кадр стека, в любое время будет только один дополнительный кадр стека? Я считаю, что C добавляет новый кадр стека для каждого вызова функции, значит ли это, что рекурсия в Scheme более эффективна в этом отношении? Если я что-то упустил, пожалуйста, дайте мне знать; это просто любопытная мысль, и я не могу посещать какие-либо курсы, посвященные этому, до следующего года. Кстати, спасибо за отличный ответ. - person Anthony Calandra; 24.01.2014
comment
Оптимизация хвостовых вызовов — это магия компилятора. Стандарт Scheme требует, чтобы компиляторы реализовали его. Оптимизация хвостового вызова реализована с использованием инструкций перехода вместо вызова. Как следствие, оптимизированная рекурсия хвостового вызова более эффективна. - person Bhaskar; 24.01.2014
comment
А, значит, если нет хвостовой рекурсии (как в первой функции), то эффективность рекурсии в Scheme такая же, как и в C? - person Anthony Calandra; 24.01.2014
comment
В нем больше деталей, интерпретируется Scheme и компилируется C. При прочих равных инструкции перехода будут быстрее, чем вызов функции, или рекурсия без хвостовой TCO будет хуже. Компилируемый GCC, вероятно, реализует рекурсию без TCO, которая быстрее, чем интерпретаторы Scheme. - person Bhaskar; 24.01.2014
comment
Попался. Кажется, теперь я понимаю разницу. Спасибо! - person Anthony Calandra; 24.01.2014
comment
Схема @Bhaskar не требует интерпретации, и существует несколько компиляторов. - person molbdnilo; 24.01.2014

arrow_upward
2
arrow_downward

Да, вызову в позиции, отличной от хвоста, нужно добавить что-то в стек, чтобы он знал, как возобновить работу, когда вызов возвращается. (Более подробное объяснение стеков, хвостовых вызовов и не-хвостовых вызовов см. в статье Стила Развенчание мифа о «дорогих вызовах процедур», или Реализация вызовов процедур считается вредной, или Лямбда: окончательный переход ссылка на странице лямбда-документов на readscheme.org.)

Но Racket (и многие другие схемы и некоторые другие языки) реализуют «стек», так что даже если у вас есть глубокая рекурсия, у вас не закончится место в стеке. Другими словами, у Racket нет переполнения стека. Одна из причин этого заключается в том, что методы поддержки глубокой рекурсии совпадают с методами поддержки продолжений первого класса, которых также требует стандарт Scheme. Вы можете прочитать о них в Стратегии реализации для первоклассных продолжений Clinger et al.

person Ryan Culpepper    schedule 24.01.2014
comment
Я понятия не имел, что у Racket не может быть переполнения стека... спасибо! Я прочитаю некоторые документы, которые вы предоставили в эти выходные. - person Anthony Calandra; 24.01.2014