VPF::Хвостовая рекурсия - Форум программистов

arcsupport

Дата 16.10.2010, 18:07 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 725
Регистрация: 24.10.2008

Репутация: нет
Всего: 2

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

kemiisto

Дата 16.10.2010, 18:25 (ссылка)

(нет голосов)

Загрузка ...

Дикий Кот. =^.^=

Награды: 1

Профиль
Группа: Участник Клуба
Сообщений: 3292
Регистрация: 29.7.2007

Репутация: нет
Всего: 160

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

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

Код


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);
}

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

Скопипастил из Вики, лень было что-то сочинять.

--------------------

XMPP-канал.

Unit testing isn't enough. You need static typing.

Пей, кури, пиши на си! smile

arcsupport

Дата 16.10.2010, 18:58 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 725
Регистрация: 24.10.2008

Репутация: нет
Всего: 2

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

GoldFinch

Дата 17.10.2010, 01:40 (ссылка)

(нет голосов)

Загрузка ...

Профиль
Группа: Завсегдатай
Сообщений: 2141
Регистрация: 30.11.2008

Репутация: нет
Всего: 26

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

cardinal

Дата 17.10.2010, 02:45 (ссылка)

(нет голосов)

Загрузка ...

Инженер

Профиль
Группа: Экс. модератор
Сообщений: 6003
Регистрация: 26.3.2002
Где: Германия

Репутация: 5
Всего: 99

Код


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);
}

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

--------------------

Немецкая оппозиция потребовала упростить натурализацию иммигрантов
В моем блоге: Разные истории из жизни в Германии

"Познание бесконечности требует бесконечного времени, а потому работай не работай - все едино". А. и Б. Стругацкие

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Алгоритмы \| Следующая тема »