递归和尾递归

luda 15-09-19
    

递归和尾递归:
递归过程中父过程中套有子过程,子过程中又套有子过程,一直套下去直到边界条件处才能返回,这种调用不能立即返回,如果一直到达不了边界而无法返回(出栈)的话,一次次的入栈却不见出栈总有一天栈溢出。

尾递归是在函数的最后一行递归,最后一行下面不会再有代码了,就是说当前这个函数中的变量所占的那些栈空间不会再有人访问了,下一个子过程不用为它的变量再入一层新栈而直接覆写父过程中的变量占用的那层栈就不会有逻辑错误的。
让我们想象运行时的景象看图说话,图在脑子里。我根本不会数学,我只会过电影似的那样思考问题。我根本无法证明什么但我能心里预演在心中制造空间图形然后像过电影似的让它们运行。我不清楚专业名词的意思,我只会想象,想象尾递归时所基于的唯一原则是:如果父过程所占用的栈空间不会再被父过程访问了那么子过程就可以覆写它。

举例:
f(n) = f(n - 1) + f(n -2)和f(n) = n + f(n -1)这种应该不可以尾递归,因为父过程中还在使用父过程所占用的栈中的那个变量n空间位置,所以子过程不能覆写父过程占用的栈空间。在f(n) = f(n - 1) + f(n -2)中,每一层过程的运行时中的n变量的值都是存储在各自当前过程对应的栈中的某个位置的,当前过程用到那个n值时就到那个n变量栈位置读取一穿长度为int的01串转化为int值然后减1然后传入f(n - 1)中去。如果允许f(n - 1)子过程去覆写父过程的那个存储n值的那个栈位置的话,那么父过程下面再往f(n - 2)中传入值的时候将会传进去错误的值。如果是f(n) = 1 + f(n - 1)这样的话是可以尾递归的。因为子过程覆写父过程的栈不会发生错误,1是常量,再怎么覆写还是1,那个栈内存地址中的值还是1并没有变,不会导致计算结果错误。如果是f(n, a) = f(n -1, n*a)这种的话也可以尾递归,因为它符合那个想象中的唯一的原则“父过程所占用的栈空间不会再被父过程访问了那么子过程就可以覆写它”。在此时此刻之前我并不理解尾递归,我只是随时随地像过电影似的计算得到的这些知识而已。



时空管子:尾递归等于迭代
尾递归是有一根管子在传结果。这根管子就是那个被父子过程重用的栈空间的那个相同空间位置。这根管子是时空管子,这根管子穿越所有父子过程的栈空间的同一个位置,这根管子的一端处在过去,一端处在未来,cpu读写当前子过程对应的栈空间的那个位置的时候是当前过程的“现在”。
这是一根时空管子。这根时空管子就是迭代过程所共享的那些变量空间。就是for循环体内的过程访问的那些共享变量空间。

尾记:我们自己内部的知识结构体系系统中不能缺少某一层的知识,必须应该是完备的,一个完备的知识系统是支持我们随时随地计算的。即使开始的时候它很小,但是由于它近乎完备,它可以随时随地计算出新知识,它可以慢慢长大。