什么是合理的方法来提高解决递归问题？ [英] What are reasonable ways to improve solving recursive problems?

问题描述

我想解决的顶部codeR网站的算法问题。我可以实现大部分的基本递归问题，如回溯，DFS ......但是，每当我遇到一个复杂的递归，往往需要我几个小时。而当我检查其它codeRS的解决方案，我觉得很羞愧自己。我一直在编程了近5年。我可以看到在其他编程技术的显著的改善，如操作字符串，图形，图形用户界面...但不递归？任何人都可以分享一些经验，如何处理递归问题？谢谢！

I like solving algorithm problems on TopCoder site. I can implement most of the basic recursive problems such as backtracking, dfs... However, whenever I encounter a complex recursion, it often takes me hours and hours. And when I check the solution of other coders, I feel so shame on myself. I've been programming for almost 5 years. I can see the significant improvement on other programming technique such as manipulating string, graphics, GUI ... but not recursion? Can anyone share some experiences how to approach a recursive problems? Thanks!

更新

我熟悉的单元测试方法。即使在我知道的单元测试，我经常写一些小的测试功能，看看结果是什么，我想。当面对递归问题，我失去了这种能力自然。我可以插入几个COUT语句来查看当前的结果，而是在通话深层嵌套的，我再也不能保持它的轨道。所以大部分的时间，无论是我解决了它使用铅笔和纸第一或我受够了（不能用常规的方法一样分解成更小的碎片）。我觉得递归要工作的全过程。

I'm familiar with Unit-Test methodology. Even before I knew Unit Test, I often write some small test functions to see if the result is what I want. When facing recursive problems, I lost this ability naturally. I can insert several "cout" statements to see the current result, but when the call is nested deeply, I no longer can keep track of it. So most of the time, either I solved it using pencil and paper first or I'm done ( can't use regular method like breaking it into smaller pieces ). I feel like recursion has to work as a whole.

最好的问候，
成龙

Best regards,
Chan

推荐答案

这是一个很好的问题。

最好的答案我已经是融通：分而治之。这是一个有点棘手，在C ++中，因为它不支持高阶功能不错，但你可以做到这一点。最常见的程序是像地图和褶皱。 [C ++已经拥有了cofold所谓的std ::积累。

The best answer I have is factoring: divide and conquer. This is a bit tricky in C++ because it doesn't support higher order functions well, but you can do it. The most common routines are things like maps and folds. [C++ already has a cofold called std::accumulate].

其他的事情，你必须仔细考虑的是如何构建code，以在可能情况下提供尾递归。谁都会很快就认识到尾调用和把它们想象成回路，这样可以减少大脑超负荷来自世界各地的递归颇有几分。

The other thing you have to consider carefully is how to structure your code to provide tail recursion where possible. One soon gets to recognize tail calls and think of them as loops, and this reduces the brain overload from recursing everywhere quite a bit.

另外一个很好的技术称为的的信任的。这意味着，你写了一个电话给你甚至可能不会定义还没有一个功能，你的的信任的，它会做你想做的事不宜迟。例如，你相信它会参观一棵树自下而上的节点正确，即使它有打电话给你目前正在写的功能。写评论，说明什么pre和后置条件的。

Another good technique is called trust. What this means is, you write a call to a function you may not even have defined yet, and you trust that it will do what you want without further ado. For example you trust it will visit the nodes of a tree bottom up correctly, even if it has to call the function you're currently writing. Write comments stating what the pre- and post-conditions are.

另一种方式做到这一点（我很抱歉关于这一点）是使用真正的编程语言如ocaml的或哈斯克尔，再试着翻译了漂亮干净的code到C ++。这样，您就可以看到的结构更容易没有得到陷入了看家的细节，丑陋的语法，缺乏本土化的，和其他的东西。一旦你拥有了它的权利，你可以将其转化为C ++机械。 （或者你可以使用费利克斯翻译给你）

The other way to do this (and I'm sorry about this) is to use a real programming language like Ocaml or Haskell first, then try to translate the nice clean code into C++. This way you can see the structure more easily without getting bogged down with housekeeping details, ugly syntax, lack of localisation, and other stuff. Once you have it right you can translate it to C++ mechanically. (Or you can use Felix to translate it for you)

我说对不起的..如果你这样做，你会不想写C ++的多了，这将使它很难找到满意的工作的原因。例如，在OCaml中，只需添加一个列表的元素（不使用倍）：

The reason I said I'm sorry is .. if you do this you won't want to write C++ much anymore, which will make it hard to find a satisfying job. Example, in Ocaml, just add elements of a list (without using a fold):

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 *)

这是不是尾递归，但这是：

This isn't tail recursive, but this is:

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 ++，也许你可以在c它跨$ C $。（单独的算法结构应该足以找出语法）

The transformation above is well known. The second routine is actually simpler when you understand what it is doing. I'm too lazy to translate this into C++, perhaps you can transcode it.. (the structure of the algorithms alone should be enough to figure out the syntax)

这篇关于什么是合理的方法来提高解决递归问题？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！