将这个递归函数转换为迭代函数。

Question

我该如何将这个递归函数转换为迭代函数？

#include <cmath>

int M(int H, int T){
    if (H == 0) return T;
    if (H + 1 >= T) return pow(2, T) - 1;
    return M(H - 1, T - 1) + M(H, T - 1) + 1;
}

这是一个三行代码，但对我而言很难将其转换为迭代函数。因为它有两个变量，并且我对 Stacks 一无所知，所以无法转换。

我的目的是提高函数的速度。该函数太慢了。我想使用 map 来加快速度，但我有三个变量 M、H 和 T，所以无法使用 map。

- user3274384

---

你可以通过模拟一个栈来实现这一点... - Angew is no longer proud of SO

@Angew 你的意思是通过堆栈模拟递归。在我看来，除非能够找到这个序列的第n个元素的公式，否则这种情况下将其转换为迭代的唯一方法就是使用堆栈。 - Spook

@user3274384 推荐你阅读一本关于数据结构或编程的书籍。这里在SO上有一个很好的C++书籍列表。就你提出的问题而言，它并不适合在SO上提问。我们主要是帮助你解决自己遇到的问题，而不是为你解决任务。 - Angew is no longer proud of SO

@user3274384 你为什么认为迭代会更快？ - David Heffernan

拥有仅限于1个声望并不意味着你所询问的所有问题都是作业。 - user3274384

Answer 1

你可以使用 动态规划 - 当H == 0和T == 0时，从下往上计算M并迭代它们。这里有一个链接，解释了如何在斐波那契数列问题中进行动态规划，这与你的问题非常相似。

- WeaselFox

---

维基百科建议使用map来加速递归函数。但在这种情况下，我实际上有3个变量：M、H和T。我该如何将它们保存到map中？ - user3274384

@user3274384 - 向下滚动，在地图解决方案之后，您可以看到自底向上迭代的伪代码。 - WeaselFox

@user3274384 要么使用 std::pair<int, int>，要么自己封装 H 和 T。在后一种情况下，您还需要为您的包装类专门化 std::hash。 - JorenHeit

Answer 2

检查一下，对于我迄今为止提供的所有输入，递归和非递归版本都给出了相等的结果。思路是将中间结果保存在矩阵中，其中H是行索引，T是列索引，而值是M(H,T)。顺便说一句，您可以计算一次，以后只需从矩阵中获取结果，这样您就可以拥有O（1）性能。

int array[10][10]={{0}};

int MNR(int H, int T)
{
    if(array[H][T])
       return array[H][T]; 

    for(int i =0; i<= H;++i)
    {
        for(int j = 0; j<= T;++j)
        {
            if(i == 0)
                array[i][j] = j;

            else if( i+1 > j)
                array[i][j] = pow(2,j) -1;

            else
                array[i][j] = array[i-1][j-1] + array[i][j-1] + 1;

        }
    }

    return array[H][T];
}

int M(int H, int T)
{
    if (H == 0) return T;
    if (H + 1 >= T) return pow(2, T) - 1;
    return M(H - 1, T - 1) + M(H, T - 1) + 1;
}

int main()
{
    printf("%d\n", M(6,3));
    printf("%d\n", MNR(6,3));
}

- Dabo

---

你可以创建一个类来封装数组、初始化和 operator()。 - Jarod42

我会保留给OP :) - Dabo

你可以使用一维数组。 - Khurshid

@Khurshid 二维数组的好处在于，所有的计算都可以一次完成，然后通过索引获取它们，这似乎是使用一维数组不可能实现的。 - Dabo

Answer 3

除非您知道序列中第n个（在本例中为(m,n)）元素的公式，否则最简单的方法是使用堆栈模拟递归。

代码应如下所示：

#include <cmath>
#include <stack>

struct Data
{
public:
    Data(int newH, int newT)
        : T(newT), H(newH)
    {

    }

    int H;
    int T;
};

int M(int H, int T)
{
    std::stack<Data> st;

    st.push(Data(H, T));

    int sum = 0;

    while (st.size() > 0)
    {
        Data top = st.top();
        st.pop();

        if (top.H == 0) 
            sum += top.T;
        else if (top.H + 1 >= top.T)
            sum += pow(2, top.T) - 1;
        else
        {
            st.push(Data(top.H - 1, top.T - 1));
            st.push(Data(top.H, top.T - 1));
            sum += 1;
        }
    }

    return sum;
}

- Spook

---

这将比递归函数慢，因为CPU堆栈内存在推送和弹出时几乎没有开销，而std::stack在推入时必须进行堆内存分配。 - Skizz

我回答的原始问题只涉及从递归版本转换为迭代版本，我的代码也只是这样做 :) - Spook

@user3274384 你一定是复制错了什么：在你的版本中，M(5, 2)不会递归，并且应该只在他的版本中运行一次。两者都不应该花费任何明显的时间。（当然，在全局范围内，他的解决方案比递归更差，无论是执行时间还是可理解性。你应该能够将至少一个递归展开成一个简单的循环，并将任何中间值保存在某种缓存中，因为原始代码多次重新计算相同的值。） - James Kanze

@user3274384 https://ideone.com/k5BED3 - 请注意，我已经完全复制了您的代码（除了函数名称）。 - Spook

已经在时间间隔0<=t,h<25内对此答案进行了计时，迭代版本比递归版本慢4.5倍。 - Skizz

Answer 4

这个函数执行缓慢的主要原因是它具有指数复杂度，并且不断地重新计算相同的成员。一种可能的解决方法是使用记忆化模式（在C++中用例子方便地解释here）。其思想是将每个结果存储在一个具有快速访问的结构中（例如一个数组），并且每次需要再次使用它时，检索已经预先计算好的结果。当然，这种方法受限于内存的大小，所以对于非常大的数字它无法工作...

在您的情况下，我们可以做类似的事情（保留递归但记忆化结果）：

#include <cmath>
#include <map>
#include <utility>

std::map<std::pair<int,int>,int> MM;

int M(int H, int T){
    std::pair<int,int> key = std::make_pair(H,T);
    std::map<std::pair<int,int>,int>::iterator found = MM.find(key);
    if (found!=MM.end()) return found->second; // skip the calculations if we can
    int result = 0;
    if (H == 0) result = T;
    else if (H + 1 >= T) result = pow(2, T) - 1;
    else result = M(H - 1, T - 1) + M(H, T - 1) + 1;
    MM[key] = result;
    return result;
}

关于时间复杂度，C++的映射是树映射，因此在其中搜索的时间复杂度为N*log(N)，其中N是映射的大小（已计算出结果的数量）。C++还有哈希映射，它们是STL的一部分，但不是标准库的一部分，正如SO上已经提到的那样。哈希映射承诺具有恒定的搜索时间（该常数值未指定），因此您也可以尝试使用它们。

- Ashalynd

---

我在这里遇到了一个错误: return (*found); : 不存在适当的转换函数，将“std::pair<const std::pair<int, int>, int>”转换为“int”。为什么？ - user3274384

糟糕，我的错，对C++有点生疏了，已经修正答案。 - Ashalynd

使用它来计算M(100,1000)，结果溢出了int（和long），但是它在很短的时间内完成了。你将给这个函数多大的值？ - Ashalynd

Answer 5

你可以使用一维数组进行计算。简单的理论，

Let F(a,b) == M(H,T)
1. F(0,b) = b
2. F(a,b) = 2^b - 1, when a+1 >= b
3. F(a,b) = F(a-1,b-1) + F(a,b-1) + 1

Let G(x,y) = F(y,x)  ,then
1. G(x,0) = x                 // RULE (1)
2. G(x,y) = 2^x - 1, when y+1 >= x  // RULE (2) 
3. G(x,y) = G(x-1,y-1) + G(x-1,y) + 1  // RULE(3) --> this is useful, 
// because for G(x,y) need only G(x-1,?), i.e if G - is two deminsions array, then 
// for calculating G[x][?]   need only  previous row G[x-1][?], 
// so we need only last two rows of array.

// Here some values of G(x,y)  
4. G(0,y)  = 2^0 - 1 = 0  from (2) rule.
5. G(1,0)  = 1  from (1) rule.
6. G(1,y) = 2^1 - 1 = 1,  when y > 0,  from (2) rule.

G(0,0) = 0,  G(0,1) = 0,   G(0,2) = 0,  G(0,3) = 0  ...
G(1,0) = 1,  G(1,1) = 1,   G(1,2) = 1,  G(1,3) = 1  ...

7. G(2,0) = 2  from (1) rule
8. G(2,1) = 2^2 - 1 = 3   from (2) rule
9. G(2,y) = 2^2 - 1 = 3 when y > 0,  from (2) rule.

G(2,0) = 2,  G(2,1) = 3,  G(2,2) = 3, G(2,3) = 3, ....

10. G(3,0) = 3  from (1) rule
11. G(3,1) = G(2,0) + G(2,1) + 1 = 2 + 3 + 1 = 6  from (3) rule
12. G(3,2) = 2^3 - 1 = 7,  from (2) rule

现在，如何计算G（x，y）？

int M(int H, int T ) { return G(T,H); }

int G(int x, int y)
{   
     const int MAX_Y = 100; // or something else
     int arr[2][MAX_Y] = {0} ; 
     int icurr = 0, inext = 1;

     for(int xi = 0; xi < x; ++xi)
     {
          for( int yi = 0; yi <= y ;++yi) 
          {
            if ( yi == 0 )  
                 arr[inext][yi] = xi; // rule (1);
            else if ( yi + 1 >= xi ) 
                 arr[inext][yi] = (1 << xi) - 1; // rule ( 2 )
            else arr[inext][yi] = 
                arr[icurr][yi-1] + arr[icurr][yi] + 1; // rule (3)

          }
          icurr ^= 1; inext ^= 1;          //swap(i1,i2);
     }
     return arr[icurr][y];
}

// 或者一些优化

int G(int x, int y)
{
    const int MAX_Y = 100;
    int arr[2][MAX_Y] = {0};
    int icurr = 0, inext = 1;

    for(int ix = 0; ix < x; ++ix)
    {
        arr[inext][0] = ix; // rule (1)

        for(int iy = 1; iy < ix - 1; ++ iy) 
            arr[inext][iy] = arr[icurr][iy-1] + arr[icurr][iy] + 1; // rule (3)

        for(int iy = max(0,ix-1); iy <= y; ++iy)
            arr[inext][iy] = (1 << ix ) - 1; // rule(2)

        icurr ^= 1 ; inext ^= 1;
    }

     return arr[icurr][y];
}

- Khurshid