Сокращение использования стека в рекурсивной функции в C++

Question

У меня есть программа, которая рассчитывает факториал любого числа. Когда я пытаюсь сделать это с большим числом, таким как 100 000, оно останавливается, прежде чем оно достигнет 0. Я предполагаю, что это какой-то механизм безопасности для предотвращения чего-то плохого.

Хотя это хорошо, это мешает программе вычислять огромные числа. В моей программе после переменной x достигает 0, останавливает рекурсивную функцию. Таким образом, нет необходимости в этой "сети безопасности".

Вот мой код для справки:

#include <iostream>
#include <string>

int answer = 1;
int recursive(int x);
using std::cout;
using std::cin;
int main() {

    recursive( 100000 );

}


int recursive( int x ) {
    cout << x << "\n";
    answer = x * answer;
    x--;
    if ( x > 0 ) {
        recursive( x );
    }
    else {
        cout << "Answer: " << answer << "\n";
    }
}

Есть ли способ исправить это препятствие?

Answer 1

Как уже упоминали другие, вы не сможете вписаться в факториал 100,000 в 64-битный тип, так как для его представления требуется около 1,5 миллиона бит. (Это число с примерно 25000 нули в конце.)

Однако предположим, что мы изменили задачу на рекурсивное сложение из [1..100000], Вы по-прежнему столкнетесь с проблемой стека. Стек является конечным, и рекурсия использует стек, поэтому существует фундаментальное ограничение на количество вызовов, которые вы можете сделать.

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

Код должен быть изменен на:

#include <iostream>
#include <string>

int answer = 1;
int recursive(int multiplier, int x=1);
using std::cout;
using std::cin;

int main() {

    std::cout << "Recursion result = " << recursive(100000) << std::endl;

}


int recursive(int multiplier, int x) {
    if (multiplier == 1) {
        return x;
    }
    return recursive(multiplier - 1, multiplier * x); // Change the * to + for experimenting with large numbers that could overflow the stack
}

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

Answer 2

Может быть, я немного опоздал, но я все же добавлю свои советы и решения. Это может помочь вам (и другим) в другой раз.
Лучшее решение проблемы stackru - вообще не использовать рекурсию:

int fac(int n){
    int res=1;
    for(int i = 0; i <= n; ++i){
        res *= i;
    }
    return res;
}

На самом деле рекурсия во время программирования не выполняется, так как она тратит время (вызовы функций) и ресурсы (стек). Во многих случаях рекурсии можно избежать, используя циклы и стек с простыми операциями pop / push, если необходимо сохранить "текущую позицию" (в C++ можно использовать vector). В случае факториала стек даже не нужен, но если вы, например, выполняете итерацию по древовидной структуре дерева, вам понадобится стек (зависит от реализации).

Теперь другая проблема у вас есть ограничение размера int: ты не можешь идти выше fac(12)если вы работаете с 32-битными целыми числами и не вышеfac(20) для 64-битных целых чисел. Это может быть решено с помощью внешних библиотек, которые реализуют операции для больших чисел (например, библиотека GMP или Boost.multiprecision, как упоминалось в SenselessCoder). Но вы также можете создать свою собственную версиюBigInteger-подобный класс из Java и реализующий основные операции, подобные той, что у меня есть. В моем примере я только реализовал умножение, но сложение очень похоже:

#include <iostream>
#include <vector>
#include <stdio.h>
#include <string>
using namespace std;


class BigInt{
    // Array with the parts of the big integer in little endian
    vector<int> value;
    int base;
    void add_most_significant(int);
    public:
        BigInt(int begin=0, int _base=100): value({begin}), base(_base){ };
        ~BigInt(){ };
        /*Multiply this BigInt with a simple int*/
        void multiply(int);
        /*Print this BigInt in its decimal form*/
        void print();
};

void BigInt::add_most_significant(int m){
    int carry = m;
    while(carry){
        value.push_back(carry % base); 
        carry /= base;
    }
}

void BigInt::multiply(int m){
    int product = 0, carry = 0;
    // the less significant part is at the beginning
    for(int i = 0; i < value.size(); i++){
        product = (value[i] * m) + carry;
        value[i] = product % base;
        carry = product/base;
    }
    if (carry)
        add_most_significant(carry);
}

void BigInt::print(){
    // string for the format depends on the "size" of the base (trailing 0 in format => fill with zeros if needed when printing)
    string format("%0" + to_string(to_string(base-1).length()) + "d");

    // Begin with the most significant part: outside the loop because it doesn't need trailing zeros
    cout << value[value.size()-1];
    for(int i = value.size() - 2; i >= 0; i-- ){
        printf(format.c_str(), value[i]);
    }
}

Основная идея проста, BigInt представляет большое десятичное число, разрезая его представление с прямым порядком байтов на части. Длина этих частей зависит от выбранной вами базы. Это будет работать только в том случае, если ваша база имеет степень 10: если вы выберете 10 в качестве базы, каждая фигура будет представлять одну цифру, если вы выберете 100 (= 10^2) в качестве базы, каждая фигура будет представлять две последовательные цифры, начиная с конца (см. little endian), если вы выберете 1000 в качестве основы (10^3), каждая часть будет представлять три последовательные цифры, ... и так далее. Допустим, у вас есть база 100, тогда будет 12765 [65, 27, 1]1789 будет [89, 17]505 будет [5, 5] (= [05,5]), ... с основанием 1000: 12765 будет [765, 12]1789 будет [789, 1]505 будет [505],
Умножение тогда немного похоже на умножение на бумаге, которое мы изучали в школе:

1. начать с самого низкого куска BigInt
2. умножить его с множителем
3. самая низкая часть этого продукта (= модуль продукта основание) становится соответствующей частью конечного результата
4. "большие" части этого продукта будут добавлены к продукту следующих частей
5. перейти к шагу 2 со следующей частью
6. если не осталось ни одного куска, добавьте оставшиеся большие куски произведения последнего куска BigInt до конечного результата

Например:

9542 * 105 = [42, 95] * 105
    lowest piece = 42 --> 42 * 105 = 4410 = [10, 44]
                ---> lowest piece of result = 10
                ---> 44 will be added to the product of the following piece
    2nd piece = 95    --> (95*105) + 44 = 10019 = [19, 00, 1]
                ---> 2nd piece of final result = 19
                ---> [00, 1] = 100 will be added to product of following piece
    no piece left --> add pieces [0, 1] to final result
==> 3242 * 105 = [42, 32] * 105 = [10, 19, 0, 1] = 1 001 910

Если я использую класс выше, чтобы вычислить факториалы всех чисел от 1 до 30, как показано в коде ниже:

 int main() {
    cout << endl << "Let's start the factorial loop:" << endl;
    BigInt* bigint = new BigInt(1);
    int fac = 30; 
    for(int i = 1; i <= fac; ++i){
        bigint->multiply(i);
        cout << "\t" << i << "! = ";
        bigint->print();
        cout << endl;
    }
    delete bigint;
    return 0;
}

это даст следующий результат:

Let's start the factorial loop:
    1! = 1
    2! = 2
    3! = 6
    4! = 24
    5! = 120
    6! = 720
    7! = 5040
    8! = 40320
    9! = 362880
    10! = 3628800
    11! = 39916800
    12! = 479001600
    13! = 6227020800
    14! = 87178291200
    15! = 1307674368000
    16! = 20922789888000
    17! = 355687428096000
    18! = 6402373705728000
    19! = 121645100408832000
    20! = 2432902008176640000
    21! = 51090942171709440000
    22! = 1124000727777607680000
    23! = 25852016738884976640000
    24! = 620448401733239439360000
    25! = 15511210043330985984000000
    26! = 403291461126605635584000000
    27! = 10888869450418352160768000000
    28! = 304888344611713860501504000000
    29! = 8841761993739701954543616000000
    30! = 265252859812191058636308480000000

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

Answer 3

Я могу предложить пару вещей для некоторых проблем, которые вы видите.

Проблема в том, что вы не можете оценить каждый рекурсивный шаг, потому что у вас переполнение стека. Это происходит, когда вы используете больше места в стеке, чем предполагалось. Вы можете избежать этого, сохранив таблицу предварительно рассчитанных значений. Обратите внимание, что это не поможет, если вы сразу захотите вычислить факториал 100000, но если вы медленно поднимитесь к нему, вычислив, например, 10!, то 20! и т.д. у вас не будет этой проблемы. Еще одна вещь, которую нужно сделать, - увеличить размер вашего стека. Я видел некоторые комментарии по этому поводу, поэтому я не буду упоминать, как.

Следующая проблема, с которой вы столкнетесь, заключается в том, что вы не сможете представить числа, полученные в результате факториала. Это потому, что вашего целочисленного размера недостаточно для представления этих чисел. Другими словами, вы переполняете целое число. Для этого, а также для пункта выше, вы можете увидеть это: Boost.multiprecision. Boost - очень хорошая библиотека, которую вы можете использовать для подобных вещей.