2020-02-29关于递归的一些理解
2020-02-29 本文已影响0人
计算机工程制图
-
背景
- 今天搞迭代和递归搞得头皮发麻，有了一些感悟，记录如下
-
感悟
- 感觉程序中设计的递归大类有两种，一种是严格数学意义上的递归。比如
n!=n*(n-1)!，就是如果想得到第n项可以通过递归的方式由第n-1项来。反应到程序上就是想解决当前规模为n的问题，必须先解决规模为n-1的问题。也就是一直递归下去直到递归基，然后回归的过程中不断解决。其实本质来讲就是递到递归基，再由递归基归到n规模问题。本质上这个归的过程其实就是迭代。如果把n规模放在上，递归基放在下。这种递归必须向从上递到下，然后从下在归到上才能得到结果。这种递归怎么改迭代哪，就是直接手动找到那个下面的递归基直接往上迭代就是了。但是这不容易，尤其是对非线性递归来说。比如阶乘这种线性的就好办。斐波那契那种二分的递归也好办。但是类似归并排序，这种，就有点难办了。我觉得这种有递有归的才是真正的递归。 - 还有另一种递归就是更偏向于程序意义上的递归了。就是在函数中调用了本身就叫递归。比如二分查找递归版或者快速排序。这种根本不像递归，姑且称上述的递归为真递归，规模为n的问题如何解决，必须先解决了n-1规模的问题，然后组合一些n提供的信息才能解决n的问题。有递有归。而本段的递归，姑且称为伪递归，感觉本质是分而治之减而治之的直接体现，就是一个大问题先解决了一部分或者排除了一部分，然后得到了一个缩小了规模的同类问题，然后这样一直解决下去直到递归基，到目前为止，问题已经解决了，根本无需回归。只有递的过程。比如所谓把一个数组逆序的递归
void reverse(int *a,int lo,int hi){swap(a[lo],a[hi]},reverse(a,lo+1,hi-1)}。还有二分查找的递归，快速排序的递归，感觉都是递的过程一步步把问题解决掉一部分，然后得到同类的规模变小的子问题，然后等递到递归基时问题已经解决了，之后的归就几乎没有或者只是简单的返回值罢了。 - 不对，上面说的好像有失偏驳。这么讲吧，我好想有点懂了，递归的本质是什么，自己调用自己，其实本质就是减而治之或分而治之的思想。只不过侧重点不同。有得侧重递，有得侧重归。不妨称为递递归，和归递归。递递归就是重在分，通过巧妙的把大问题分成同类型小问题，使小问题之间几乎是独立的。当小问题解决了，它的上一个层次的问题自然而然解决了。所以当递到递归基的时候，整个问题已经解决了。典型的如快速排序。而归递归的特点就是分同类型小问题时很简单，几乎什么事情也没做。然后分到递归基，之后通过一层一层的小问题的组合，直到回到最终的大问题。问题才得到 解决。显然，归递归重在归，及组合。典型如归并排序。暂时只能理解到这个层次了。
- 感觉程序中设计的递归大类有两种，一种是严格数学意义上的递归。比如
