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、尾递归

        当递归调用是整个函数体中最后执行的语句且它的返回值不属于表达式的一部分时，这个递归调用就是尾递归。尾递归函数的特点是在回归过程中不用做任何操作，递归结果可以直接返回。编译器在处理尾递归的时候，不会不听的创建栈帧，而是去覆盖之前的栈帧，《算法精解》里面的原话就是："When a compiler detects a call that is tail recursive, it overwrites the current activation record instead of pushing a new one onto the stack.
        将上面的斐波那契数列方法改成尾递归，

    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的时候，我们通过断点可以得到下面的界面：

递归与尾递归 recursive & tail recursive插图

 

这里我们可以，每次执行，都会记录一次栈帧，最终结果自然是：

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方法，我么会得到

递归与尾递归 recursive & tail recursive插图1

从上面的执行结果来看，我们可以看到每次执行并不会创建新的栈帧，而是复用了之前的栈帧。

我们将这个方法用java实现会发现：

递归与尾递归 recursive & tail recursive插图2

    这也就是为什么在scala里面可以使用尾递归，同样的程序，我们在使用java编写却会出现问题，原因就是我们上面所说的，现在的java编译器并不支持尾递归优化，而scala则支持了尾递归优化

 

45 对 “递归与尾递归 recursive & tail recursive”的想法；

  16. Pingback： brand name cialis
  18. Pingback： sildenafil canada

  20. I’ll immediately snatch your rss as I can’t
    to find your e-mail subscription link or newsletter
    service. Do you’ve any? Please let me recognize
    in order that I may just subscribe. Thanks.

    回复

  21. I truly love your site.. Great colors & theme.

    Did you develop this amazing site yourself?
    Please reply back as I’m attempting to create my very own website and would love to know where you got
    this from or just what the theme is named. Appreciate it!

    回复

  24. I don’t even know how I stopped up here, but I assumed this submit used to be good. I do not recognise who you are but certainly you’re going to a famous blogger should you are not already 😉 Cheers!

    回复

  26. I have been surfing online more than 2 hours today, yet
    I never found any interesting article like yours. It’s
    pretty worth enough for me. In my opinion, if all site owners
    and bloggers made good content as you did, the net will be much more useful than ever before.

    回复

  28. It’s tthe est tike to mke a feew plans ffor thhe lonjg runn
    and it’s timne tto bbe happy. I hae lean this submit and if Ickuld
    I desiree too recommed yoou some fasinating iswsues orr suggestions.
    Perhaps youu can wrife next articles relpating too thi article.
    I want to leazrn even more thinfs about it!

    回复

  33. Hello! I’ve been reading your site for a long time now and finally got the
    courage to go ahead and give you a shout out from Atascocita Texas!

    Just wanted to mention keep up the good job!

    回复

  36. One thing is one of the most typical incentives for making use of your cards is a cash-back and also rebate offer. Generally, you’ll have access to 1-5 back on various buying. Depending on the credit cards, you may get 1 returning on most purchases, and 5 in return on expenses made going to convenience stores, filling stations, grocery stores along with ‘member merchants’.

    回复

  40. He gօes to sleep early, yеs I children you not. Hᥱ from the Boisy Doisy Hot Shoe
    Shuffle and Berry Ⲥlub Ꮪhake, ups stumps well prior to midnight and takes themsᥱlves to bedroom.
    We were all іn such shoc ouг company had to acquire yet anothеr draft beer to soothe our
    nerves.

    回复

  45. It’s appropriate time to make some plans for the future and it’s
    time to be happy. I’ve read this post and if I could
    I desire to suggest you few interesting things or
    advice. Perhaps you can write next articles referring to this
    article. I wish to read more things about it!

    回复

发表评论

邮箱地址不会被公开。