将此递归函数转换为迭代

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;
}

嗯,它是一个3行代码,但我很难将其转换为迭代函数.因为它有2个变量.而且我什么都不知道Stacks所以我无法转换它.

我这样做的目的是提高功能的速度.这个功能太慢了.我想用map,使这个速度更快,但我有3个变量M,H并且T让我不能使用map

Answer 1

你可以使用dynamic programming- 当H == 0时自下而上开始,T == 0计算M并迭代它们.这是一个解释如何为Fibonacci数字执行此操作的链接,这与您的问题非常相似.

Answer 2

检查一下,递归和非递归版本为我到目前为止提供的所有输入提供了相同的结果.我们的想法是将中间结果保存在矩阵中,其中H是行索引,T是col索引,值是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));
}

Answer 3

这个函数缓慢的主要原因是它具有指数复杂度，并且它不断地一次又一次地重新计算相同的成员。一种可能的解决方法是记忆模式（此处用 C++ 示例轻松解释）。这个想法是将每个结果存储在一个可以快速访问的结构中（例如数组），并且每次您再次需要它时，检索已经预先计算的结果。当然，这种方法受到内存大小的限制，因此它不适用于极大的数字......

对于您的情况，我们可以做类似的事情（保留递归但记住结果）：

#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 中已经提到的那样。哈希映射承诺恒定的搜索时间（虽然未指定常量的值:)），所以您也可以尝试一下。