《程序设计基础(C99)》:
例如,当需要求f(n)=1+2+3+…+n的值时,由于这个问题可以简化成n+f(n—1),而且当n为1时问题的答案f(1)明显为1,这样的问题就呵以视为已经解决了。而具体的求解方法则可以由n=1时的解答f(1)得到n=2时问题的解答(f(2)=2+f(1)=3),再由f(2)可以求得f(3)=3+f(2)=6……只要n为有限值,总能得到最终所要求的解答。如果把问题的不断简化的过程(把对于n的问题简化成对于n—1的问题的过程)理解为“递”的话,那么从“递”的终止点(f(1)=1)开始,求f(2),再由f(2)求得f(3)……直到求得f(n)的这个过程就是“归”。“递”的终点就是“归”的起点。
因此,递归也是人类的一种思维方式,同样递归有时也是描述解决问题的方法的一种方式。当解决问题的方法可以用递归的方式来描述时,在程序中使用递归技术来解决问题也就顺理成章了。
1.递归是函数对自身的调用
使用递归的前提是具备递归的思想,办即用递归的方法思考解决问题的方法和步骤,而程序则是对这种方法和步骤的自然描述。在程序实现上,递归就是函数通过对自身的调用来描述自己的函数定义。
很多人都听过这样的故事:
“从前有个山,山里有个庙,庙里有个老和尚给小和尚讲故事。讲的什么呢?”
“从前有个山,山里有个庙,庙里有个老和尚给小和尚讲故事。讲的什么呢?”
“从前有个山,山里有个庙,庙里有个老和尚给小和尚讲故事。讲的什么呢?”
这是个明显的递归的例子。在每次讲到“讲的什么呢?”之后,又开始讲故事,而讲的故事恰恰是刚刚阱过的内容。如果把讲故事的过程抽象为一个函数,那么在函数完成“讲的什么呢?”之后的行为,就完全可以用对自身的调用来实现。
……
展开