递归与尾递归 recursive & tail recursive
1、什么是递归
编程语言中,函数Func(Type a,……)直接或间接调用函数本身,则该函数称为递归函数。在数学上,关于递归函数的定义如下:对于某一函数f(x),其定义域是集合A,那么若对于A集合中的某一个值X0,其函数值f(x0)由f(f(x0))决定,那么就称f(x)为递归函数。
或者这么说递归递归是为了细分一个任务,将任务拆解成为一个有规律的,有相同解法的问题
2、递归能解决什么问题
public static long factorial(long n){
if(n==1){
return 1;
}
return n*factorial(n-1);
}
使用递归是一个非常有效的解决特定问题的途径,但是递归的局限性很让程序员很苦恼,随着程序语言的发展,慢慢的,一种解决递归内存占用的解决方案出现了。那就是尾递归,tail recursive。
3、尾递归
public static long factorial(long n,long a){
if(n==1){
return a;
}
return factorial(n-1, n*a);
然而如果你认为尾递归就解决这个问题的话,就打错特错了。据了解,老牌程序语言在编译器里,并不支持尾递归的优化,所以即使你在这一类的程序语言里使用了尾递归,也不会得到想要的结果,比如,JAVA,C。等等大佬。
下面的例子让你更直观了解尾递归优化和递归的处理方式,这里我们选择了scala
def main(args: Array[String]): Unit = { val result = stackOverFlow(1) println(result) } /** * recursive * * @param o * @return */ def stackOverFlow(o: Int): Int = { val result = o + 1 if (result < 100000) stackOverFlow(result) result } /** * tail recursive * * @param o * @return */ def tailStack(o: Int): Int = { val result = o + 1 if (result > 100000) result else tailStack(result) }
这里涉及了两个简单的方法,一个stackOverFlow方法(递归),一个tailStack方法(尾递归),当我们在调用stackOverFlow的时候,我们通过断点可以得到下面的界面:
这里我们可以,每次执行,都会记录一次栈帧,最终结果自然是:
Exception in thread “main” java.lang.StackOverflowError
at demo4.RecursionDemo$.stackOverFlow(RecursionDemo.scala:19)
at demo4.RecursionDemo$.stackOverFlow(RecursionDemo.scala:19)
at demo4.RecursionDemo$.stackOverFlow(RecursionDemo.scala:19)
at demo4.RecursionDemo$.stackOverFlow(RecursionDemo.scala:19)
at demo4.RecursionDemo$.stackOverFlow(RecursionDemo.scala:19)
at demo4.RecursionDemo$.stackOverFlow(RecursionDemo.scala:19)
at demo4.RecursionDemo$.stackOverFlow(RecursionDemo.scala:19)
at demo4.RecursionDemo$.stackOverFlow(RecursionDemo.scala:19)
at demo4.RecursionDemo$.stackOverFlow(RecursionDemo.scala:19)
at demo4.RecursionDemo$.stackOverFlow(RecursionDemo.scala:19)
at demo4.RecursionDemo$.stackOverFlow(RecursionDemo.scala:19)
然后我们在运行 tailStack方法,我么会得到
从上面的执行结果来看,我们可以看到每次执行并不会创建新的栈帧,而是复用了之前的栈帧。
我们将这个方法用java实现会发现:
这也就是为什么在scala里面可以使用尾递归,同样的程序,我们在使用java编写却会出现问题,原因就是我们上面所说的,现在的java编译器并不支持尾递归优化,而scala则支持了尾递归优化