переполнение стека хвостовой рекурсии

Question

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

Answer 1

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

int braindeadrecursion(int n)
{
  if (n == 0)
    return 1;

  return braindeadrecursion(n - 1);
}

Эта функция довольно проста;он просто возвращает 1. Без оптимизаций на моем компьютере генерируется код, который выглядит примерно так:

_braindeadrecursion:
00  pushq   %rbp
01  movq    %rsp,%rbp
04  subq    $0x10,%rsp
08  movl    %edi,0xf8(%rbp)
0b  movl    0xf8(%rbp),%eax
0e  cmpl    $_braindeadrecursion,%eax
11  jne 0x0000001c
13  movl    $0x00000001,0xfc(%rbp)
1a  jmp 0x0000002e
1c  movl    0xf8(%rbp),%eax
1f  subl    $0x01,%eax
22  movl    %eax,%edi
24  callq   _braindeadrecursion
29  movl    %eax,%ecx
2b  movl    %ecx,0xfc(%rbp)
2e  movl    0xfc(%rbp),%eax
31  addq    $0x10,%rsp
35  popq    %rbp
36  ret

Как видите, рекурсивный вызов находится в 0x24.Теперь давайте попробуем с более высокой оптимизацией:

_braindeadrecursion:
00  pushq   %rbp
01  movq    %rsp,%rbp
04  movl    $0x00000001,%eax
09  popq    %rbp
0a  ret

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

Answer 2

Либо: - вы можете увеличить размер стека, либо - не использовать рекурсию, а вместо этого использовать какой-то цикл.