Hun*_*ter 42 algorithm recursion recursive-datastructures data-structures
我在思考/解决递归问题时遇到了麻烦.我真的很欣赏这个概念,我可以理解它们,比如创建基本案例,退出案例和递归调用等.我可以解决简单的问题,比如在数组中编写阶乘或整数求和.这就是我的想法停止的地方.当问题变得复杂时,我无法真正应用概念或提出解决方案.例如,河内的塔,虽然我能理解问题和解决方案,但我,我自己无法解决问题.它也适用于其他算法,如快速排序/二叉树遍历.所以我的问题是
请指教.
Pau*_* Bu 43
递归只是一种思考方式,就像迭代一样.当我们在学校的孩子时,我们没有被教导递归思考,而且存在真正的问题.你需要将这种思维方式融入你的武器库,一旦你这样做,它将永远留在那里.
我发现总是首先弄清楚基本情况是有用的,也许起初它们不是最简单的情况,但是一旦你开始在该基本情况的基础上构建递归,你就会意识到你可以简化它.识别基本情况的重要性在于,首先,您要关注最简单形式需要解决的问题(更简单的情况),并以某种方式绘制未来算法的路线图,其次,确保算法停止.也许不会返回预期的结果,但至少会停止,这总是令人鼓舞.
此外,它总是有助于弄清楚问题的一个小实例将如何帮助您找到更大问题实例的解决方案.例如,如何为n已经输入解决方案的输入构建解决方案n-1.
解决您可以递归思考的每个问题.是的,Hanoi Towers不是一个很好的例子,它的递归解决方案是一个非常聪明的解决方案.尝试更容易的问题,几乎是元素问题.
但最重要的是,从简单的问题开始.几乎每个问题都有递归解决方案.数学问题很难掌握它.每次看到for循环或while循环时,将该算法转换为递归.
函数式编程在很大程度上依赖于递归.我不认为这应该有多大帮助,因为它们本身就是递归的,对于那些不太理解递归的用户来说可能很麻烦.
使用一种简单的编程语言,一种你最熟悉的编程语言,最好是一种不会因内存烦恼和指针而烦恼的编程语言.在我看来,Python是一个非常好的开始.很简单,打字或复杂的数据结构不会打扰你.只要该语言可以帮助您专注于递归,它就会更好.
最后一条建议,如果找不到问题的解决方案,可以在互联网上搜索或寻求帮助,完全了解它的作用并转移到另一个.不要让他们绕过你,因为你要做的就是将这种思维方式融入你的脑海.
要掌握递归,你需要先掌握递归 :)
希望这可以帮助!
Yve*_*ust 10
我的建议:相信递归函数"完成工作",即满足其规范.知道这一点,您可以构建一个功能,解决更大的问题,同时仍然满足规范.
你如何解决河内塔问题？假设有一个功能Hanoi(N)能够在不违反规则的情况下移动一堆N盘.使用此功能,您可以轻松实现河内'(N + 1):执行河内(N),移动下一个磁盘并再次执行河内(N).
如果河内(N)工作,那么河内'(N + 1)也可以工作,而不会违反规则.要完成参数,必须确保递归调用已终止.在这种情况下,如果你可以非递归地解决河内(1)(这是微不足道的),你就完成了.
使用这种方法,您不必担心事情将如何实际发生,您可以保证它的工作原理.(前提是您转移到越来越小的问题实例.)
另一个例子:二叉树的递归遍历.假设该功能Visit(root)完成了这项工作.然后,if left -> Visit(left); if right -> Visit(right); print root将完成这项工作!因为第一个调用将打印左子树(不要担心如何),第二个调用将打印右子树(不要担心如何),并且根也将打印.
在后一种情况下,终止是通过处理越来越小的子树,直到叶子的事实来保证的.
其他例子:Quicksort.假设您有一个对数组进行就地排序的函数,让Quicksort.您将按如下方式使用它:在大型元素之前移动小元素,就地,通过将它们与精心选择的"pivot"值进行比较(实际上,数组中的任何值都可以).然后通过Quicksort函数对大元素进行排序,并以相同的方式对大元素进行排序,您就完成了!无需怀疑将要发生的分区的确切顺序.如果避免使用无效子阵列,则可确保终止.
最后一个例子,Pascal的三角形.你知道元素是它上面两个元素的总和,边上是1.所以闭着眼睛,C(K, N)= 1 if K=0 or K=N, else C(K, N) = C(K-1, N-1) + C(K, N-1).而已 !