优化尾部递归

虽然都是靠自己,但不同形式的尾部递归,在堆栈上的表现还是大有不同的。有的更容易造成堆栈溢出,而有的却相当友好。至于怎么优化,慢慢来看。

从最基本的概念说起,每个线程都有一个堆栈,这个堆栈的高低取决于它所调用的函数的情况。举例来说,此线程先调用了函数甲,函数甲一个人心有余而力不足,无法独自完成所有的任务,它又请求了函数乙的帮助。出来借的,总归是要还的。每次往外的调用,都会使堆栈增长,就像欠下的债一样。调用的太多了,就会负债累累,非崩盘不行。

基本套路看完后,就可以看看尾部递归的招数啦。如果一个函数在运行到最后一步的时候才力不足,那么它请人帮忙的行为就被叫做尾部调用。如果尾部调用的对象是它自己,它就成为了尾部递归。尾部递归,不像其他的尾部调用,它造成堆栈溢出的可能性更大,因为自己调用自己,简单快捷方便,不用见外。找别人的时候,首先得需要这个人存在。此外,即便有人了,也得好意思张开那个嘴才成。所以一般不是递归的时候,堆栈的增长都是很有限的。

最后就要说说优化了。其实可以这样想,假如老大找老二帮忙,老二又得找老三。如果老二对老三这样说,“你这件事做完,直接给老大就行了,不用来找我”,那么,这一系列的调用就优化了。反之,如果老二说,“你做完之后,先给我,我再做点补充,然后再给老大。”,这样一来,就不优化了。递归是同样的道理,不过把老大,老二和老三都看成同一个人就行了。

显而易见,优化的手段就是减少中间步骤,把任务传达的干干净净。

王辉 wechat
交流或订阅,请长按或扫描上方微信二维码