Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Алгоритмы > Хвостовая рекурсия

Автор: arcsupport 16.10.2010, 18:07

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

Автор: kemiisto 16.10.2010, 18:25

Понимаете верно. Вот Вам яркий пример.

Пишем рекурсивную функцию для вычисления факториала:

Код


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

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

Переписываем:

Код


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

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

Скопипастил из http://ru.wikipedia.org/wiki/%D0%A5%D0%B2%D0%BE%D1%81%D1%82%D0%BE%D0%B2%D0%B0%D1%8F_%D1%80%D0%B5%D0%BA%D1%83%D1%80%D1%81%D0%B8%D1%8F, лень было что-то сочинять.

Автор: arcsupport 16.10.2010, 18:58

А как число Фибоначчи посчитать таким образом, а функцию Аккермана?

Автор: GoldFinch 17.10.2010, 01:40

arcsupport, никак. Надо чтоб был только один рекурсивный вызов.

Автор: cardinal 17.10.2010, 02:45

Код


int fibloop(int x, int y, int i, int n)
{ if (i> n) 
   return y;
  else
   return fibloop(y, x+y, i+1, n);
} 

int fib(int n)
{ return fibloop(1,1,2,n);
}

а вот Аккермана наверно никак...