首页 >后端开发 >php教程 >对递归的思考和疑惑。

对递归的思考和疑惑。

WBOY
WBOY原创
2016-06-06 20:30:03900浏览

背景:

  • 求10的阶乘,我们可以用递归来处理,就是从f(10)到f(1)的过程,当算到f(1)的时候开始返回计算。
  • 递归删除一个文件夹,其实是循环遍历文件夹来删除文件。

思考和疑惑:

我能理解递归其实是一个压栈的过程。那么,我的问题:
1. 求10的阶乘的过程,当算到f(1)的时候为什么要继续返回去计算?因为到了栈顶,为了返回到栈底必须返回继续计算。
可是这样解释怎么会很牵强。
我的理解是因为f(2)在等着f(1)的值,以此类推,f(10)在等f(9)的值,所以要返回继续计算。

2.递归删除文件夹,因为递归是一个同步操作的过程,所以我们也可以把循环理解为一个压栈的过程,那么递归删除文件夹真的和求10的阶乘的思路一样吗,求阶乘是因为f(10)在等f(9)的值而去返回操作,但是删除文件返回却是因为循环导致的要返回操作。

求真:以上是我的理解,理解对或者不对,恳请各位大大帮我指正,并给出宝贵意见,谢谢大家。

回复内容:

背景:

  • 求10的阶乘,我们可以用递归来处理,就是从f(10)到f(1)的过程,当算到f(1)的时候开始返回计算。
  • 递归删除一个文件夹,其实是循环遍历文件夹来删除文件。

思考和疑惑:

我能理解递归其实是一个压栈的过程。那么,我的问题:
1. 求10的阶乘的过程,当算到f(1)的时候为什么要继续返回去计算?因为到了栈顶,为了返回到栈底必须返回继续计算。
可是这样解释怎么会很牵强。
我的理解是因为f(2)在等着f(1)的值,以此类推,f(10)在等f(9)的值,所以要返回继续计算。

2.递归删除文件夹,因为递归是一个同步操作的过程,所以我们也可以把循环理解为一个压栈的过程,那么递归删除文件夹真的和求10的阶乘的思路一样吗,求阶乘是因为f(10)在等f(9)的值而去返回操作,但是删除文件返回却是因为循环导致的要返回操作。

求真:以上是我的理解,理解对或者不对,恳请各位大大帮我指正,并给出宝贵意见,谢谢大家。

递归的原因是,当你在计算的过程中需要一个值的时候,发现这个值还需要(同样的)计算来得到,……如此下去,直到最终所有参与计算的值都不需要再计算来得到为止。

递归的表现是函数调用,函数调用的必然过程就是栈操作。

阶乘

以阶乘来说,其实阶乘用一个简单的循环是很容易算出来的,实际应用中根本不需要用到递归。但用它来作为例题,只是为了说明递归的原理 n! = n * (n - 1)!,所以要算 n 的阶乘就要先算 n - 1 的阶乘,直到 1(因为1的的阶乘定值 1,不需要再计算——其实如果不考虑初始 n = 1 的情况,直接算到 2 就好了)。这样一来就形成了一个递归运算,函数表达式为 f(n) = n * f(n - 1)(这里的函数即表示数学函数,也表示程序语言的函数)

删除目录

删除目录也是一样的道理,你要删除外层目录,除非这个目录里面已经没有目录或者文件了,所以可以把这个过程看过是两个步骤

  1. 清空目录的内容 empty(d)
  2. 删除空目录 delete(d)

再来看 emtpy(d) 要干什么呢,要删除 d 下面的目录和文件,即(算法描述)

<code>empty(d) => {
    (foreach c in d.children) => {
        if c is directionry deleteDir(c)
        else deleteFile(c)
    }
}
</code>

deleteFile 很简单,不详述

deleteDir 又要干什么呢——清空目录,删除目录,即

<code>deleteDir(d) => {
    empty(d)
    delete(d)
}
</code>

注意到 empty()deleteDir() 相互都有调用,所以它们两个组成了一个多函数的递归,当某个目录下面再无子目录的时候,foreach 语句中不会再调用 deleteDir,这就成为递归的终结点。

最终的过程,当然是按目录层层下找,但是却是从最底层开始删除,层层回退

当然,如果用栈+循环的方式也很好解决,找到文件直接删除,找到目录就压栈,找完之后栈顶一定是个空目录,依次出栈删除即可。

声明:
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn