改进解决递归问题的合理方法是什么？

Question

我喜欢在 TopCoder 网站上解决算法问题。我可以实现大部分基本的递归问题，例如回溯、dfs……但是，每当我遇到复杂的递归时，往往会花费我几个小时的时间。当我检查其他程序员的解决方案时，我为自己感到羞愧。我从事编程已经快 5 年了。我可以看到其他编程技术的显着改进，例如操作字符串、图形、GUI……但不是递归？谁能分享一些如何解决递归问题的经验？谢谢！

更新

我熟悉单元测试方法。甚至在我知道单元测试之前，我就经常编写一些小测试函数，看看结果是否是我想要的。当面对递归问题时，我自然就失去了这个能力。我可以插入几个“cout”语句来查看当前结果，但是当调用嵌套得很深时，我无法再跟踪它。所以大多数时候，要么我先用铅笔和纸解决它，要么我就完成了（不能使用常规方法，例如将其分成小块）。我觉得递归必须作为一个整体来工作。

谨致问候，
陈

Answer 1

我发现铅笔和纸非常方便。将问题分解为更小的块也是一个好主意，例如使用非常小的数据集。您应该做的第一件事是确定您的基本条件，即标记递归调用结束的条件。从那里，您可以处理递归问题的主体，并使用更大的数据集测试/验证它。

我还想补充一点，速度并不是成为一名优秀工程师的唯一资格。工程师还可以拥有许多其他技能，包括跳出框框观察和思考的能力、说服他人采取特定行动方案的能力、分解问题并向外行（利益相关者和客户）解释的能力等等。更多的。

Answer 2

这是一个很好的问题。

我的最佳答案是分解：分而治之。这在 C++ 中有点棘手，因为它不能很好地支持高阶函数，但你可以做到。最常见的例程是地图和折叠之类的东西。 [C++ 已经有一个名为 std::accumulate 的 cofold]。

您必须仔细考虑的另一件事是如何构建代码以尽可能提供尾递归。人们很快就会认识到尾部调用并将它们视为循环，这大大减少了到处递归所造成的大脑过载。

另一种好的技术称为“信任”。这意味着，您编写了对一个您可能还没有定义的函数的调用，并且您相信它将毫不费力地执行您想要的操作。例如，您相信它会自下而上正确地访问树的节点，即使它必须调用您当前正在编写的函数。写下注释，说明前置条件和后置条件。

另一种方法（对此我很抱歉）是首先使用真正的编程语言，例如 Ocaml 或 Haskell，然后尝试将干净的代码转换为 C++。通过这种方式，您可以更轻松地查看结构，而不会陷入内务细节、丑陋的语法、缺乏本地化和其他问题的困境中。一旦你掌握了它，你就可以将它机械地翻译成 C++。 （或者你可以用Felix帮你翻译）

我说对不起的原因是..如果你这样做了你就不想再写太多C++了，这将很难找到一份满意的工作。例如，在 Ocaml 中，只需添加列表的元素（不使用折叠）：

let rec addup (ls: int list) : int = match ls with 
| [] -> 0                (* empty list *)
| h::t -> h + addup t    (* add head to addup of tail: TRUST addup to work *)

这不是尾递归，但这是：

let addup (ls: int list) : int = 
  let rec helper ls sum = match ls with
  | [] -> sum
  | h :: t -> helper t (h+ sum)
  in
helper ls 0

上面的转换是众所周知的。当您了解第二个例程在做什么时，它实际上会更简单。我懒得把它翻译成C++，也许你可以转码它..（仅算法的结构就足以弄清楚语法）

Answer 3

问题的哪些部分花费了您数小时的时间？

其他编码员的解决方案你自己没有弄清楚吗？

作为一般建议，请记住考虑基本情况，然后记住您认为在每个递归级别必须保持的不变量。由于在递归调用中未正确保留不变量，因此经常会出现错误。

Answer 4

我曾经参加过一个为喜欢编程的疯狂青少年举办的夏令营。他们教给我们解决问题（递归和其他）的“法国方法”（内部参考）。

1）用你自己的话定义你的问题，并做一些可行的例子。

2) 进行观察，考虑边缘情况、约束（例如：“算法在最坏情况下必须为 O(n log n)”）

3) 决定如何解决问题：图论、动态规划（递归）、组合硝化组学。

从这里开始，具体递归：

4）识别“子问题”，根据约束猜测可能有多少子问题，并用它来猜测通常会很有帮助。最终，一个子问题将在你的脑海中“咔哒”一声。

5) 选择自下而上或自上而下的算法。

6）代码！

在整个这些步骤中，一切都应该用好笔写在纸上，直到第 6 步。在编程比赛中，那些立即开始敲击的人通常表现不佳。

步行总是能帮助我找出算法，也许它也会对你有帮助！

Answer 5

获取小阴谋家的副本并开始工作通过练习。

不要因为本书使用Scheme 而不是C++ 或C# 或任何您最喜欢的语言而被推迟。 Douglas Crockford 说道（早期版本，名为The Little LISPer):

1974 年，丹尼尔·P·弗里德曼 (Daniel P. Friedman) 发表了
一本名为《The Little》的小书
LISPer。。虽然只有68页，但
做了一件了不起的事情：它可以教导
你要递归地思考。它使用了一些
LISP 的假装方言（这是
那时全部大写）。
方言不完全符合
任何真正的 LISP。但这没关系，因为
这与 LISP 无关，而是
关于递归函数。

Answer 6

尝试在 c++0x 中自动记忆:)。原帖： http://slackito.com/2011/03/ 17/automatic-memoization-in-cplusplus0x/

和我的递归函数 mod：

#include <iostream>
#include <functional>
#include <map>

#include <time.h>

//maahcros
#define TIME(__x) init=clock(); __x; final=clock()-init; std::cout << "time:"<<(double)final / ((double)CLOCKS_PER_SEC)<<std::endl;
#define TIME_INIT  clock_t init, final;
void sleep(unsigned int mseconds) { clock_t goal = mseconds + clock(); while (goal > clock()); }

//the original memoize
template <typename ReturnType, typename... Args>
std::function<ReturnType (Args...)> memoize(std::function<ReturnType (Args...)> func)
{
    std::map<std::tuple<Args...>, ReturnType> cache;
    return ([=](Args... args) mutable  {
        std::tuple<Args...> t(args...);
        if (cache.find(t) == cache.end()) {
            cache[t] = func(args...);
        }
        return cache[t];
    });
}

/// wrapped factorial
struct factorial_class {

    /// the original factorial renamed into _factorial
    int _factorial(int n) {
        if (n==0) return 1;
        else {
         std::cout<<" calculating factorial("<<n<<"-1)*"<<n<<std::endl;
         sleep(100);
         return factorial(n-1)*n;
        }
    }

    /// the trick function :)
    int factorial(int n) {
        if (memo) return (*memo)(n);
        return _factorial(n);
    }

    /// we're not a function, but a function object
    int operator()(int n) {
        return _factorial(n);
    }

    /// the trick holder
    std::function<int(int)>* memo;

    factorial_class() { memo=0; }
};

int main()
{
 TIME_INIT
    auto fact=factorial_class(); //virgin wrapper
    auto factorial = memoize( (std::function<int(int)>(fact) ) ); //memoize with the virgin wrapper copy
    fact.memo=&factorial; //spoilt wrapper
    factorial = memoize( (std::function<int(int)>(fact) ) ); //a new memoize with the spoilt wrapper copy

    TIME ( std::cout<<"factorial(3)="<<factorial(3)<<std::endl; ) // 3 calculations
    TIME ( std::cout<<"factorial(4)="<<factorial(4)<<std::endl; ) // 1 calculation
    TIME ( std::cout<<"factorial(6)="<<factorial(6)<<std::endl; ) // 2 calculations
    TIME ( std::cout<<"factorial(5)="<<factorial(5)<<std::endl; ) // 0 calculations

    TIME ( std::cout<<"factorial(12)="<<factorial(12)<<std::endl; )
    TIME ( std::cout<<"factorial(8)="<<factorial(8)<<std::endl;  )
    return 0;
}

Answer 7

• 识别基本情况：即识别何时停止递归的情况。

  例如： if (n == null) { return 0; }

• 通过将问题分解为尽可能小的情况来识别子问题。

那么我们可以通过两种方式来解决，通过编码

• 头递归
• 尾递归

在head recursive方法中，递归调用然后处理。在处理第一个节点之前，我们处理列表的“其余部分”。这使我们能够避免在递归调用中传递额外的数据。

在尾递归方法中，处理发生在递归调用之前

Answer 8

我认为最好避免递归。在大多数情况下，循环更优雅且更容易理解。循环也更高效，长循环不会因堆栈溢出错误而导致程序崩溃。

我发现递归是最优雅的解决方案的问题很少。通常此类问题与图形或表面上的导航有关。幸运的是，这个领域已经被研究得很透彻，所以你可以在网上找到大量的算法。

当在包含不同类型节点的一些更简单的图形（如树）中导航时，访问者模式通常比递归更简单。

Answer 9

动态规划有帮助。记忆也很有帮助。