如何统计递归调用次数？Java幂函数递归计数异常问题排查

AI 小北

2026-7-21

问题分析

你当前的power方法用的是线性递归：每次调用都把指数减1，直到指数为0。这种实现下，递归调用次数等于指数 + 1（比如指数9时，从9到0共10次调用），这和你预期的5次不符。

你说的预期5次，对应的是分治快速幂的实现——利用指数的奇偶性拆分问题，把递归深度从O(n)降到O(log₂n)，这才是你遗漏的核心逻辑。

修改后的实现

import java.util.Scanner;
public class Power1 {
   public static int count = 0;
   public static void main(String[] args) {
      Scanner scanner = new Scanner(System.in);   
      System.out.print("Please enter the base value: ");
      double base = scanner.nextDouble();
      System.out.print("Please enter the non-negative integer exponent value: ");
      int exp = scanner.nextInt();
      
      double result = power(base, exp);
      
      System.out.println(base + " raised to the power of " + exp 
                         + " is: " + result);
      System.out.println("A total of " + count + " recursive calls "
                         + "were made to the power method.");
   }
   
   static double power(double base, int exp) {
      count++;
      // 基例：任何数的0次方都是1
      if (exp == 0) 
         return 1;
      
      // 递归处理：拆分指数
      double half = power(base, exp / 2);
      if (exp % 2 == 0) {
          // 偶数指数：base^exp = (base^(exp/2))^2
          return half * half;
      } else {
          // 奇数指数：base^exp = base * (base^((exp-1)/2))^2
          return base * half * half;
      }
   }
}

验证结果

当输入底数2、指数9时，递归调用链是：