尾递归

简书 賈小強
转载请注明原创出处，谢谢！

什么是尾递归

递归 的本质是某个方法调用了自身，每次调用将问题变小，直到能够直接解决
尾递归 是递归中的一种特殊形式，其要求为：某个方法调用自身这件事，一定是该方法做的最后一件事

1，当有需要返回值的时候会是return f(n)，没有返回的话就直接是f(n)了
2，return f(n)外不能加其他东西，否则就不是最后一件事了
比如有返回值的，你不能乘个常数n 如 return n*f(n)；甚至是 f(n)+f(n-1)

//没有使用尾递归的形式
def recsum(x):
  if x == 1:
    return x
  else:
    return x + recsum(x - 1)

//使用尾递归的形式
def tailrecsum(x, running_total=0):
  if x == 0:
    return running_total
  else:
    return tailrecsum(x - 1, running_total + x)

尾递归优化的原因

1，因为在递归调用自身的时候，这一层函数已经没有要做的事情了，虽然被递归调用的函数是在当前的函数里，但是他们之间的关系已经在传参的时候了断了，也就是这一层函数的所有变量什么的都不会再被用到了，所以当前函数虽然没有执行完，不能弹出栈，但它确实已经可以出栈了

2，正因为调用的是自身，所以需要的存储空间是一毛一样的，那干脆重新刷新这些空间给下一层利用就好了，不用销毁再另开空间

Java没有尾递归优化的原因

As explained by Brian Goetz (Java Language Architect at Oracle) :

in jdk classes [...] there are a number of security sensitive methods that rely on counting stack frames between jdk library code and calling code to figure out who's calling them.

Anything that changed the number of frames on the stack would break this and would cause an error. He admits this was a stupid reason, and so the JDK developers have since replaced this mechanism.

He further then mentions that it's not a priority, but that tail recursion

will eventually get done.

N.B. This applies to HotSpot and the OpenJDK, other VMs may vary.

Happy learning !!