C++ 将递归函数重写为非递归 - 涉及 MPIR 并且非常困难

Question

我很难将一个函数从递归转换为非递归使用 MPIR 的库变量“mpz_t”而不是“unsigned __int64”的函数。我也在考虑我应该如何编写循环。当我让它成为递归时，这很容易，但当我试图让它成为非递归时，就很难了!

unsigned __int64 exampleFunc( unsigned __int64 a,
                              unsigned __int64 b,
                              unsigned __int64 c )
{
    if( a <= 2 )
        return a + 1;
    if( b <= 4 )
        return b;
    if( c == 3 )
        return c - 1;
    if( b == 5 )
        c += 2;
    // How will I put these into a loop?
    return exampleFunc( a - 1, b - 2, c ) + exampleFunc( 0, b + 1, c - 1 );
};

部分问题在于我们无法编写返回 mpz_t 值的函数。我们只能向它写入一个值(如指针)。所以，像这样不会工作:

mpz_t exampleFunc( ... );

这意味着，像这样的东西可以工作:

void exampleFunc( mpz_t out, ... );

或者甚至是全局变量(不强烈推荐):

mpz_t g_out;
mpz_init( g_out );
void exampleFunc( ... ) { g_out = ? };

注意:

我们应该尽量不使用数组甚至 vector ，因为数字会非常非常大——这解释了为什么我要从 unsigned __int64 切换到 mpz_t。除非我们真的必须...

请帮忙，我真的很紧张。谢谢。

Answer 1

关于 gmp 的问题:尝试使用 gmpxx.h - 你可以像返回整数一样返回 mpz_class 对象。

mpz_class withgmp( const mpz_class &a, const mpz_class &b, mpz_class c )
{
    if( a <= 2 )
        return a + 1;
    if( b <= 4 )
        return b;
    if( c == 3 )
        return c - 1;
    if( b == 5 )
        c += 2;
    return withgmp( a - 1, b - 2, c ) + withgmp( 0, b + 1, c - 1 );
}

请注意，我按值传递了 c，因为它可能在函数中被修改。

或者，如果您必须使用纯 C，您应该为结果传递第四个参数，如下所示:

void withmpz( mpz_t a, mpz_t b, mpz_t c, mpz_t result)
{
     // ... leaving out the boundary conditions
     mpz_t left; mpz_init(left);
     // ... leaving out code for adjusting a,b and c
     withmpz(a,b,c, left);
     mpz_t rightt; mpz_init(right);
     // ... leaving out code for adjusting a,b and c
     withmpz(a,b,c, right);
     mpz_add(result, left, right);
}

注意 mpz_t 看起来好像是按值传递，但实际上它总是按引用传递，所以调用 withmpz

后 a,b,c 会发生变化

你的问题的第二部分，如何将其转换为迭代，确实比较困难。一种方法是将其更改为基于堆栈的算法，其中每个迭代步骤将堆栈顶部替换为需要添加的 2 个值，直到可以立即计算出一个，然后将其添加到最终结果中，重复此操作直到你的堆栈上没有更多的值。