Является ли следующая программа рекурсивной?

Question

То, что я интерпретировал из приведенной ниже программы, это то, что она хвостовая рекурсивная, потому что в конце, когда функция возвращается, ничего не остается для оценки.Я прав?

void fun(int x) 
{ 
  if(x > 0) 
  { 
     fun(--x); 
     printf("%d\t", x); 
     fun(--x); 
  } 
} 

Answer 1

Нет.Первый рекурсивный вызов fun() должен сохранить текущее значение x, сделать новый вызов функции, передать ему копию и возобновить выполнение в области вызова.

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

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

Answer 2

ИМХО, это не хвостовая рекурсия.

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

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

Обновление:

в соответствии с https://en.wikipedia.org/wiki/Tail_call,, к хвостовой рекурсии следует обращатьсявызов.Если мы говорим о хвостовой рекурсии в точке вызова функции, первый вызов в вашей программе должен быть не хвостовым рекурсивным, тогда как второй - это вызов хвостовой рекурсии.

Но в целомПрограмма, я думаю, что это не tail recursion в целом.