本节内容
比如我们调用函数的时候,比如main函数调用add时候,需要为add分配内存,我们管这个这个叫Frame,如果add函数自己调用自己什么状态,我们管自己调用自己叫做递归,它调用的时候它会分配新的栈桢么?就是说自己调用自己的时候栈帧的状态是什么样子的?
所谓的自己调用自己是什么,只不过执行了相同的代码,但是它依然会分配新的栈帧,一直往上面分配,只不过栈帧的内存状态未必是一样的,数据可能会不一样。什么是一样的?.text中使用的代码一样的而已。如果这个递归函数不小心写错了没有中止,那么会一直往上分配,直到整个栈的空间耗光,耗光的时候会引发一种叫堆栈溢出。
每种语言甚至是每种操作系统甚至不同平台栈空间大小未必是一样的,有些可能是1MB,有些可能是10MB,go语言是1GB,另外还有些语言对它是有限制的,它不是限制栈内存耗光了,而是调用递归深度如果超出多少就会认为你是溢出了。比如python语言限制1000次。
堆栈溢出多处情况下发生在递归调用,因为递归调用写的算法有问题,可能没有明确的终止,这时候可能会形成溢出。
堆栈溢出有这样一个问题,我们写个算法,需要使用递归,我们遍历一个非常大的xml文件,比如我们以深度优先模式扫描,肯定使用递归调用不停的一级一级的扫描,扫描完一点一点的返回,当我不知道深度有多大的时候我们怎么样避免堆栈溢出呢?
比如一个树,深度控制在三层,那么你可能广度很多,深度优先之后接下来广度,这样做法堆栈依然会爆掉,你的计数器不好控制,比如计数器超过1000次就终止,那么有可能每个栈桢浪费了1MB空间,如果10MB的话执行10次就爆掉了,这样计数器没有什么用,你控制函数调用次数你怎么控制每个栈桢有多大。
很显然,这里存在一个问题是写递归的时候要非常的小心,因为不小心的情况下我们有可能会出错,而且这种出错很难恢复。比如你调试的时候拿10MB、100MB做测试,但是线上运行时可能时间长了以后数据会变得非常大,几GB、TB的都有可能,你的递归算法可能线上就会出错。所以递归算法的编写其实要非常的小心,那么通常情况下有几种方式,第一种比如go语言栈桢空间足够大,还有一种方式你得自己去优化递归算法。
我们调用一个函数,比如main函数调用add函数,当调用的时候分配栈桢空间,当调用add结束的时候,处理后就回来,回来之后这个内存就会重复使用,给下次函数调用时候使用。那我们想象下,假如说这儿有个扫描的递归函数scan,这个函数要进行递归调用,正常情况下是分配新的栈桢,再往上一种分配新的栈桢,执行完了之后一级一级再回来直到结束这样的一个过程。那么我们想象有没有这样的可能,假如说main函数调用scan,这个scan函数去调用递归的时候,比如说往上递归的时候,如果我们把返回过程去掉的话,如果不返回的话,那么这个栈桢没必要保留了,为什么?因为保存现场IP在main栈桢空间不属于scan栈桢空间。假如我们调用新的scan的时候不需要返回,那么第一个栈桢空间是不是不需要保留,他可以直接回到IP进行恢复,那么也就意味着我每次进行递归调用的时候都重复使用同一段栈桢空间,不管递归多少次都是重复使用同一段栈桢空间,因为你调用的是同一个函数,他的栈桢空间大小是一样的,因为我们知道栈桢空间是在编译期已经确定好的,编译的时候就知道这个栈桢到底有多大,如果每次调用都不返回,那么我们考虑一点这个栈桢空间不需要保留,那么每次递归调用都使用同一段内存的时候,那么不管递归多少次,栈也爆不掉。所以我们想一想怎么样重复使用这段内存,我们说过一个函数调用另外一个函数为什么会返回,我们简单的写一个例子。
- void test(){
- test()
- print("xxx")
- }
test函数调用自己,再调用一个print,这种在函数调用的时候每次都需要返回,是因为我们接下来需要调用print,test调用完比如回来才能调用print。那么它的调用过程其实是
- test
- |
- test ------+
- | test
- void test(){
- x = 1234
- test()
- }
上面这样,也就意味着test是最后一行,它执行test的时候,不管前面有什么逻辑,执行到test时候,理论上前面的内容都已经失效了,因为后面没有代码引用前面的上下文了,前面所有上下文都不要的情况下,而test是最后一行,那么当前栈桢的所有状态就可以抛弃掉。
这就是之前说的重复使用一段内存,内存里面就是存的两部分数据,一部分是局部变量,还有一部分是调用其它函数的参数,那么如果是最后一行,局部变量空间显然是不需要了,调用参数参数传递完之后这段空间也可以不要了。所以上下两部分空间都不要的情况下,那么有必要为新的调用分配新的栈桢呢,当然可以重复使用一段栈桢。
我们管这种调用方式称之为尾调用。当你的函数最后一行是一个函数调用,而且不需要处理返回值的时候,我们管这种调用称之为尾调用。尾调用的时候,编译器可能会对它进行优化,第一种方式重复使用同一个栈桢,这种方式可以避免大量分配新的栈桢,第二种方式可以把整个函数调用优化为一个循环,因为函数调用每一次用的栈的状态是一样的,那么用一个循环把函数块演变成代码块,这样也可以在同一个栈桢内使用,一个循环重复利用的是一个栈桢的本地局部变量区域。所以编译器对于尾调用一般情况下都会尝试进行优化,优化完之后用来避免递归调用。前提是你得自己去写尾调用,并不是所有编译器都能识别这种方式。
- int test(){
- x = 1234
- test() + 1
- }
假如说
这样的操作,这个算不算尾调用?这个返回值出来还需要+1操作,这个是在当前栈桢空间中操作的,那么test状态必须要保留,这种情况不能称之为尾调用。尾调用是什么,你调用一个函数不需要任何返回值的处理,后面也没有新的代码,因为我们知道
- test() + 1
可以拆分成两块
- test() + 1
实际上是由两条指令构成的。
- call test();ret+1;
最后一步是函数调用,意味着无需返回当前函数,那么当前堆栈帧就可以放弃。
不是尾调用。
- f(x)+1
来源: http://www.cnblogs.com/lyj/p/foundation_16_recursion.html