大n值下递归Stack Overflow问题修复，能否用迭代实现？

当n为较大整数时，递归实现会出现Stack Overflow问题，但小整数n可正常运行。请问该如何修复此问题？是否可以采用迭代方法实现？

用户提供的Java代码：

import java.util.Scanner;

public class XORinacci {

  public static int Rinacci(int a, int b, int n) {
    if (n == 0) return a; else if (n == 1) return b;

    return Rinacci(a, b, n - 1) ^ Rinacci(a, b, n - 2);
  }

  
  public static void main(String[] args) {
    Scanner scan = new Scanner(System.in);
    int T = scan.nextInt();
    int arr[] = new int[T];
    int a, b, n;
    for (int i = 0; i < T; i++) {
      a = scan.nextInt();
      b = scan.nextInt();
      n = scan.nextInt();
      arr[i] = Rinacci(a, b, n);
    }
    for (int i = 0; i < arr.length; i++) {
      System.out.println(arr[i]);
    }
    scan.close();
  }
}

栈溢出原因 #

你的递归实现存在两个核心问题：

• 重复计算爆炸：每次调用Rinacci(n)都会触发Rinacci(n-1)和Rinacci(n-2)，时间复杂度达到O(2^n)，计算量指数级增长。
• 调用栈深度超限：递归调用的深度等于n值，当n较大时（比如超过10000），JVM的调用栈会被耗尽，直接抛出StackOverflowError。

迭代实现方案 #

完全可以用迭代方法替代递归，只需要保存前两项的结果，逐步递推到第n项，时间复杂度O(n)，空间复杂度O(1)，彻底避免栈溢出问题。

修改后的迭代版本代码：

import java.util.Scanner;

public class XORinacci {

  public static int Rinacci(int a, int b, int n) {
    if (n == 0) return a;
    if (n == 1) return b;
    int prevPrev = a; // 对应f(0)
    int prev = b;     // 对应f(1)
    int current = 0;
    for (int i = 2; i <= n; i++) {
      current = prev ^ prevPrev;
      // 更新前两项的值，为下一次迭代做准备
      prevPrev = prev;
      prev = current;
    }
    return current;
  }

  public static void main(String[] args) {
    Scanner scan = new Scanner(System.in);
    int T = scan.nextInt();
    for (int i = 0; i < T; i++) {
      int a = scan.nextInt();
      int b = scan.nextInt();
      int n = scan.nextInt();
      System.out.println(Rinacci(a, b, n));
    }
    scan.close();
  }
}

最优方案：利用周期规律 #

观察XORinacci序列的规律：

• f(0) = a
• f(1) = b
• f(2) = a^b
• f(3) = b^(ab) = a
• f(4) = (a^b)a = b
• f(5) = a^(ab) = a^b
• ...

可以发现序列每3项就会循环：a, b, a^b, a, b, a^b...

直接根据n对3取模的结果返回对应值即可，时间复杂度O(1)，效率最高：

import java.util.Scanner;

public class XORinacci {

  public static int Rinacci(int a, int b, int n) {
    switch (n % 3) {
      case 0: return a;
      case 1: return b;
      case 2: return a ^ b;
      default: return 0; // 逻辑上不会走到此分支
    }
  }

  public static void main(String[] args) {
    Scanner scan = new Scanner(System.in);
    int T = scan.nextInt();
    for (int i = 0; i < T; i++) {
      int a = scan.nextInt();
      int b = scan.nextInt();
      int n = scan.nextInt();
      System.out.println(Rinacci(a, b, n));
    }
    scan.close();
  }
}

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