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

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++,也许你可以对它进行转码..(算法的结构本身应该足以弄清楚语法)