递归版回文判断函数为何比迭代版慢两倍多？

你遇到的这种情况很典型，逻辑完全一致但递归版耗时远超迭代版，核心原因在于递归的函数调用开销，以及JVM对尾递归优化的限制，具体可以拆解为这几点：

• 函数调用的额外开销：每次递归调用isPalindrome时，JVM都需要执行一系列额外操作：将当前方法的上下文（包括当前的left、right值、返回地址等）压入调用栈，创建新的栈帧存储新调用的参数与局部变量；调用结束后还要弹出栈帧、恢复之前的上下文。而迭代版全程在同一个方法内执行，只是修改局部变量left和right，完全没有这些栈操作的开销。

• JVM不支持尾递归优化：你的递归写法属于尾递归（方法最后一步直接调用自身，没有额外计算逻辑），但Java的HotSpot虚拟机默认不会对尾递归做优化——不像Scala、部分C++编译器那样会自动把尾递归转换为迭代逻辑。因此你的递归版本实际会执行(right-left+1)/2次完整的函数调用，每一次的栈操作开销累加起来，就导致总耗时比迭代版多了一倍多。

• 字节码执行效率差异：迭代版的循环逻辑对应的字节码非常紧凑，都是简单的变量自增、条件判断、字符读取操作；而递归版每次调用都要处理参数传递、栈帧管理，生成的字节码指令数量更多，CPU需要执行的周期也就更长，自然耗时更高。

附原代码对比 #

递归版（耗时14ms）

public boolean isPalindrome(String word, int left, int right) {
    if(left >= right) return true;
    if(word.charAt(left) != word.charAt(right)) return false;

    return isPalindrome(word, left + 1, right - 1);
}

迭代版（耗时6ms）

public boolean isPalindrome(String word, int left, int right) {
    while(left < right) {
        if(word.charAt(left) != word.charAt(right)) return false;
        
        left++;
        right--;
    }
    return true;
}

内容的提问来源于stack exchange，提问作者Tydal