Форум программистов, компьютерный форум CyberForum.ru

Хвостовая рекурсия - C++

Восстановить пароль Регистрация
 
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
07.07.2013, 13:10     Хвостовая рекурсия #1
C++
1
2
3
4
5
6
7
8
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);
}
. Можно ли в хвостатом факториале избавиться от вспомогательной функции? Как?
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
07.07.2013, 13:10     Хвостовая рекурсия
Посмотрите здесь:

Рекурсия (на С) C++
Рекурсия C++
Рекурсия C++
C++ Рекурсия
C++ Рекурсия
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
OhMyGodSoLong
~ Эврика! ~
 Аватар для OhMyGodSoLong
1234 / 983 / 42
Регистрация: 24.07.2012
Сообщений: 2,002
07.07.2013, 13:47     Хвостовая рекурсия #2
C++
1
2
3
4
int factorial(int n, int acc = 1) {
    if (n == 0) return acc;
    else return factorial(n - 1, acc * n);
}
Иначе никак.

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

Добавлено через 20 минут

Не по теме:

Правильный факториал на Си++ объектно-ориентированном Си++:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <map>
 
class fact {
    typedef std::map<int, int> memomap;
    static memomap memo;
 
    int value;
 
    static int helper(int n, int acc)
    {
        if (n == 0) return acc;
        else return helper(n - 1, acc * n);
    }
 
public:
    fact(int n)
    {
        memomap::iterator cur = memo.find(n);
        if (cur == memo.end())
        {
            memomap::iterator prev = memo.find(n - 1);
            if (prev == memo.end())
            {
                value = helper(n, 1);
            }
            else
            {
                value = n * prev->second;
            }
            memo[n] = value;
        }
        else
        {
            value = cur->second;
        }
    }
 
    operator int() const
    {
        return value;
    }
};
 
std::map<int, int> fact::memo;

taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
07.07.2013, 14:17  [ТС]     Хвостовая рекурсия #3
Зачем здесь map?
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
07.07.2013, 14:31     Хвостовая рекурсия #4
Сообщение было отмечено автором темы, экспертом или модератором как ответ
для небольших факториалов:
C++
1
2
3
4
long f(long n) 
{
   return (n & 0xFFFF) ? f( ((n & 0xFFFF)-1) | ( (n & 0xFFFF0000) ? n * (n & 0xFFFF0000) : (n << 16) ) ) : (n >> 16);
}
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
07.07.2013, 14:35  [ТС]     Хвостовая рекурсия #5
Нифига не понял.
Thinker
Эксперт C++
 Аватар для Thinker
4215 / 2189 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
07.07.2013, 15:35     Хвостовая рекурсия #6
Цитата Сообщение от taras atavin Посмотреть сообщение
Нифига не понял.
ну, это почти ваш алгоритм, только две переменные хранятся в одной
Yandex
Объявления
07.07.2013, 15:35     Хвостовая рекурсия
Ответ Создать тему
Опции темы

Текущее время: 11:42. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru