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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
#1

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

07.07.2013, 13:10. Просмотров 616. Ответов 5
Метки нет (Все метки)

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);
}
. Можно ли в хвостатом факториале избавиться от вспомогательной функции? Как?
0
Лучшие ответы (1)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
07.07.2013, 13:10
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Хвостовая рекурсия (C++):

Быстрая сортировка и хвостовая рекурсия(как реализовать?) - C++
Как реализовать хвостовую рекурсию в быстрой сортировке? К примеру вот программа быстрого поиска: void qsort (int b, int e) { ...

Чем отличается хвостовая рекурсия от обычной рекурсии? - C++
Собственно вопрос сверху. Если не затруднит, то покажите пример факториала с хвостовой и с обычной рекурсией. Буду крайне благодарен.

Рекурсия - C++
Привет. Только что узнал,что такое рекурсия и понял как она работает,но написать участок кода с рекурсией мозгов не хватает. Нужно...

Рекурсия - C++
Разработать рекурсивную функцию не возврашающую значений: Дано натуральное четное число n. Разработать функцию для вывода на экран...

Рекурсия - C++
Есть функция, в нее передается массив из n элементов. Функция находит минимальный элемент и считает сколько раз он встречается в массиве,...

рекурсия - C++
Всем доброго времени суток. Есть рекурсивная функция выводящая числа от 15 до 10 по убыванию, как сделать чтоб выводило эти же числа но...

5
OhMyGodSoLong
~ Эврика! ~
1244 / 993 / 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;

0
taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
07.07.2013, 14:17  [ТС] #3
Зачем здесь map?
0
Thinker
Эксперт С++
4227 / 2201 / 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);
}
3
taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
07.07.2013, 14:35  [ТС] #5
Нифига не понял.
0
Thinker
Эксперт С++
4227 / 2201 / 150
Регистрация: 26.08.2011
Сообщений: 3,802
Записей в блоге: 5
07.07.2013, 15:35 #6
Цитата Сообщение от taras atavin Посмотреть сообщение
Нифига не понял.
ну, это почти ваш алгоритм, только две переменные хранятся в одной
0
07.07.2013, 15:35
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.07.2013, 15:35
Привет! Вот еще темы с ответами:

РЕкурсия - C++
Мне нужно 5 задач по рекурсии с решениями,)))есмли не сложно-помогите, может ссылочку куда или что-нибудь)))заранее благодарен

Рекурсия - C++
Сегодня баловался с рекурсией. получилось типа цикла, только из функции #include &lt;iostream&gt; using namespace std; unsigned...

Рекурсия - C++
Помогите пожалуйста как это можно написать. Y=(2*n+1)!!*(2*m+1)!!/(2*(m+n)+1)!!,где m,n неотрицательные целые числа.Для определения...

Рекурсия - C++
Сделайте одну програмку используя рекурсию. Очень нужно... Срочно. 1. Реализовать поиск НОД; 2. Возвести число в целую степень; ...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
6
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru