Конвертировать рекурсию в "хвостовую рекурсию"

Ответ 1

Хотя вы часто видите следующее в качестве примера преобразования факториала в tail-call:

int factorial(int n, int acc=1) {
  if (n <= 1) return acc;
  else        return factorial(n-1, n*acc);
}

это не совсем правильно, так как это требует, чтобы умножение было как ассоциативным, так и коммутативным. (Умножение ассоциативно и коммутативно, но приведенное выше не служит моделью для других операций, которые не удовлетворяют этим ограничениям.) Лучшее решение может быть:

int factorial(int n, int k=1, int acc=1) {
  if (n == 0) return acc;
  else        return factorial(n-1, k+1, acc*k);
}

Это также служит моделью для преобразования фибоначчи:

int fibonacci(int n, int a=1, int b=0) {
  if (n == 0) return a;
  else        return fibonacci(n-1, a+b, a);
}

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

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

int mouse(int n, int a=1, int b=1, int c=1) {
  if (n <=2 ) return a;
  else        return mouse(n-1, a*c+1, a, b);
}

Addenda

В комментариях были подняты два вопроса. Я попытаюсь ответить на них (и еще один) здесь.

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

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

Это, вероятно, достаточно, чтобы заставить голову вращаться, поэтому я скажу иначе: вместо того, чтобы вставлять аргументы и возвращаемое местоположение в стек и вызывать функцию (которая позже будет возвращена), вы нажимаете аргументы и место продолжения в стек и перейти к функции, которая позже будет продолжена. Короче говоря, вы просто делаете стек явным параметром, и вам никогда не нужно возвращаться. Этот стиль программирования распространен в управляемом событиями коде (см. Python Twisted), и это настоящая боль, чтобы писать (и читать). Поэтому я настоятельно рекомендую разрешить компиляторам сделать это преобразование для вас, если вы найдете тот, который сделает это.

@xxmouse предположил, что я вытащил уравнение рекурсии из шляпы и спросил, как она была получена. Это просто оригинальная рекурсия, но переформулирована как преобразование одного кортежа:

fn = fn-1*fn-3 + 1
=>
Fn = <Fn-11*Fn-13+1, Fn-11, Fn-12>

Я не знаю, ясно ли это, но это лучшее, что я могу сделать. Посмотрите пример фибоначчи на несколько более простой случай.

@j_random_hacker спрашивает, каковы пределы этого преобразования. Он работает для рекурсивной последовательности, где каждый элемент может быть выражен некоторой формулой предыдущих элементов k, где k является константой. Существуют и другие способы создания рекурсии хвостового вызова. Например:

// For didactic purposes only
bool is_odd(int n) { return n%2 == 1; }

int power(int x, int n, int acc=1) {
  if (n == 0)         return acc;
  else if (is_odd(n)) return power(x, n-1, acc*x);
  else                return power(x*x, n/2, acc);
}

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

int squared(n) { return n * n; }

int power(int x, int n) {
  if (n == 0)         return 1;
  else if (is_odd(n)) return x * power(x, n-1));
  else                return squared(power(x, n/2));
}

Спасибо Алексею Фрунзе за следующий тест: Выход (ideone):

mouse(0) = 1
mouse(1) = 1
mouse(2) = 1
mouse(3) = 2
mouse(4) = 3
mouse(5) = 4
mouse(6) = 9
mouse(7) = 28
mouse(8) = 113
mouse(9) = 1018

Ответ 2

Используя google, я нашел эту страницу, которая описывает Tail Recursion. В принципе, вам нужно разделить функцию как минимум на две другие функции: одну, которая выполняет эту работу, сохраняя "накопление" текущего значения, а другой - драйвер для вашей функции workhouse. Факторный пример в C ниже:

/* not tail recursive */
unsigned int
factorial1(unsigned int n)
{
    if(n == 0)
        return 1;
    return n * factorial1(n-1);
}

/* tail recursive version */
unsigned int 
factorial_driver(unsigned int n, unsigned int acc)
{
    if(n == 0)
        return acc;

    /* notice that the multiplication happens in the function call */
    return factorial_driver(n - 1, n * acc);
}

/* driver function for tail recursive factorial */
unsigned int
factorial2(unsigned int n)
{
    return factorial_driver(n, 1);
}

Ответ 3

@Ответ Алексея Фрунзе в порядке, но не совсем правильно. Действительно, можно преобразовать любую программу в одну, где вся рекурсия - это хвостовая рекурсия, преобразуя ее в Continuation Passing Style.

У меня нет времени прямо сейчас, но я попытаюсь выполнить повторную реализацию вашей программы в CPS, если я получу несколько минут.

Ответ 4

Вы можете сделать что-то вроде этого:

#include <stdio.h>

void fr(int n, int a[])
{
  int tmp;

  if (n == 0)
    return;

  tmp = a[0] * a[2] + 1;
  a[2] = a[1];
  a[1] = a[0];
  a[0] = tmp;

  fr(n - 1, a);
}

int f(int n)
{
  int a[3] = { 1, 1, 1 };

  if (n <= 2)
    return 1;

  fr(n - 2, a);

  return a[0];
}

int main(void)
{
  int k;
  for (k = 0; k < 10; k++)
    printf("f(%d) = %d\n", k, f(k));
  return 0;
}

Выход (ideone):

f(0) = 1
f(1) = 1
f(2) = 1
f(3) = 2
f(4) = 3
f(5) = 4
f(6) = 9
f(7) = 28
f(8) = 113
f(9) = 1018

Компилятор может преобразовать fr() в нечто вроде этого:

void fr(int n, int a[])
{
  int tmp;

label:    

  if (n == 0)
    return;

  tmp = a[0] * a[2] + 1;
  a[2] = a[1];
  a[1] = a[0];
  a[0] = tmp;

  n--;

  goto label;
}

И это будет оптимизация хвостового вызова.

Ответ 5

Проблема заключается в том, что последняя операция не является одним из рекурсивных вызовов, а добавлением 1 к умножению. Ваша функция в C:

unsigned faa (int n)  // Ordinary recursion
{
    return n<3 ? 1 :
                 faa(n-3)*faa(n-1) + 1;  // Call, call, multiply, add
}

Если вы измените порядок, в котором запрашиваются значения, вы можете превратить один из вызовов в цикл:

unsigned foo (int n)  // Similar to tail recursion
{                     // (reverse order)
    int i;
    unsigned f;

    for (i=3, f=1; i<=n; i++)
        f = f*foo(i-3) + 1;

    return f;
}

Ключевым моментом является выбор порядка, в котором значения фактически вычисляются в исходной функции, а не в порядке, в котором они запрашиваются.

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

Хотя, "The Right Thing (TM)" здесь нужно использовать динамическое программирование, чтобы избежать вычисления одних и тех же значений много раз:

unsigned fuu (int n)  // Dynamic programming
{
    int i;
    unsigned A[4]={1,1,1,1};

    for (i=3; i<=n; i++)
    {
        memmove (A+1, A, 3*sizeof(int));
        A[0] = A[1]*A[3] + 1;
    }

    return A[0];
}

Массив A содержит скользящее окно последовательности: A [0] == f (i), A [1] == f (i-1), A [2] == f (i-2) и т.д.

memmove может быть записана как:

        A[3] = A[2];
        A[2] = A[1];
        A[1] = A[0];