Можно ли сделать каталонское число в C с хвостовой рекурсией? - PullRequest
Новая
       53

Можно ли сделать каталонское число в C с хвостовой рекурсией?

0 голосов
/ 16 ноября 2018

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

int catalan(int n){
    if(n==0){
        return 1;
    }
    else{
        return 2*(2*n-1)*Catalan(n-1)/(n+1);
    }
}

1 Ответ

0 голосов
/ 16 ноября 2018

Укажите множитель и делитель в качестве параметров для функции, 

unsigned long  catalan_tail(unsigned long  n,
                            unsigned long  multiplier,
                            unsigned long  divisor)
{
    /* Optional TODO: Divide multiplier and divisor by
                      their greatest common divisor? */

    if (n < 2)
        return multiplier / divisor;
    else
        return catalan_tail(n - 1, multiplier * 2*(2*n - 1), divisor * (n + 1));
}

и функцию-обертку 

unsigned long  catalan(unsigned long  n)
{
    return catalan_tail(n, 1, 1);
}

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

Мы должны предоставить множитель и делитель как отдельные значения, потому чтогарантируется, что результат будет только целым числом для последней итерации.

Часть "Необязательный TODO" не относится к каталонским числам как таковым, но обычно рекомендуется при работе с факториалами и умножениеми раздел.Бинарный подход для наибольший общий делитель прост в реализации и достаточно быстр, и часто помогает сохранить промежуточные значения в пределах диапазона используемого типа.

Простой способ выяснить, c = a*b переполнение, это проверка, если c/a == b (при положительном a, a >= 1).

...