将此递归函数转换为迭代 [英] Convert this recursive function to iterative

问题描述

如何将此递归函数转换为迭代函数?

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

这是一个三行代码，但是对我来说很难将其转换为迭代函数.因为它有2个变量.而且我对Stacks一无所知，因此无法转换.

Well it's a 3-line code but it's very hard for me to convert this to an iterative function. Because it has 2 variables. And I don't know anything about Stacks so I couldn't convert that.

我这样做的目的是提高功能的速度.此功能太慢.我想使用map来加快速度，但是我有3个变量M，H和T，所以我不能使用map

My purpose for doing this is speed of the function. This function is too slow. I wanted to use map to make this faster but I have 3 variables M, H and T so I couldn't use map

推荐答案

此函数很慢的主要原因是因为它具有指数级的复杂性，并且不断地重新计算相同的成员.一种可能的解决方法是记忆模式(在C ++ 此处的示例中方便地说明了).想法是将每个结果存储在具有快速访问权限的结构中(例如数组)，并且每次您再次需要它时，都检索已经预先计算的结果.当然，这种方法受内存大小的限制，因此不适用于数量很大的情况...

The main reason why this function is slow is because it has exponential complexity, and it keeps recalculating the same members again and again. One possible cure is memoize pattern (handily explained with examples in C++ here). The idea is to store every result in a structure with a quick access (e.g. an array) and every time you need it again, retrieve already precomputed result. Of course, this approach is limited by the size of your memory, so it won't work for extremely big numbers...

在您的情况下，我们可以做类似的事情(保留递归但记住结果):

In your case, we could do something like that (keeping the recursion but memoizing the results):

#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的一部分，但不是标准库的一部分，就像已经

Regarding time complexity, C++ maps are tree maps, so searching there is of the order of N*log(N) where N is the size of the map (number of results which have been already computed). There are also hash maps for C++ which are part of the STL but not part of the standard library, as was already mentioned on SO. Hash map promises constant search time (the value of the constant is not specified though :) ), so you might also give them a try.

这篇关于将此递归函数转换为迭代的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！