尾递归的局限

之前看书的时候，有看到尾递归方面的理论知识，比较有名的是作为对递归计算阶乘的优化，理论上无懈可击，是那么完美，但现实很骨感。事实是，大部分语言和编译器都不支持尾递归优化。

对于尾递归（或者说尾调用），维基百科的解释如下：

在计算机学里，尾调用是指一个函数里的最后一个动作是返回一个函数的调用结果的情形，即最后一步新调用的返回值直接被当前函数的返回结果。此时，该尾部调用位置被称为尾位置。尾调用中有一种重要而特殊的情形叫做尾递归。经过适当处理，尾递归形式的函数的运行效率可以被极大地优化。尾调用原则上都可以通过简化函数调用栈的结构而获得性能优化（称为“尾调用消除”），但是优化尾调用是否方便可行取决于运行环境对此类优化的支持程度如何。

先插个题外话，最近在细读王垠的博客，获益匪浅。在他的启发下，开始学习Scheme，所以一些小程序的代码尽量会用Scheme去写。

使用普通递归计算阶乘代码如下：

(define factorial
  (lambda (n)
    (if (= n 1)
        1
        (* n (factorial (- n 1)))
        )
    )
  )

使用尾递归优化的代码如下：

(define factorial
  (lambda (n total)
    (if (= n 1)
      total
      (factorial (- n 1) (* n total))
      )
  )
)

理想情况下，编译器会对尾递归进行优化，调用者的栈帧（可以理解为环境）里的数据不再被使用，其占用的空间完全可以被重复利用，被调用者不需再分配栈空间。递归是一个比较抽象的操作，使用者往往对调用栈的深度很难有形象的概念，因此递归操作非常容易造成栈溢出。尾递归在理论上完美解决了这一问题。

但实际上呢？

故事源于我遇到的一个编程题，题目如下：

给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
示例:
输入: [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
说明:
假设你总是可以到达数组的最后一个位置。

由于之前对于尾递归的好感，随手写了一个尾递归。

class Solution {
    public int jump(int[] nums) {
        return findMax(nums,0,0);
    }

    private int findMax(int[] nums, int index,int times) {
        if (nums[index] >= nums.length - 1 - index) {
            return 1 + times;
        }
        int max = 0;
        int maxIndex = index;
        if (nums[index] == 1) {
            maxIndex++;
        } else{
            for (int i = 0; i < nums[index]; i++) {
                if (nums[index + 1 + i] >= max) {
                    max = nums[index + 1 + i];
                    maxIndex = index + 1 + i;
                }
            }
       }
        return findMax(nums,maxIndex,times + 1);
    }
}

然后就在传入参数数组全为1且长度足够长的时候出现了栈溢出，至此我依然认为是我对尾递归的理解不到家，没有写到精髓点。于是去查资料，才发现Java根本不支持尾递归优化。而且发现不少语言和编译器都不支持尾递归优化，我没有一一去尝试，便不提具体名字。

现在我对尾递归有了更全面的认识，属于一个还没有被全面支持的完美理论。以后的代码应该尽量避开递归，多用循环实现。