Zibonacci递归函数实现遇栈溢出问题求助

核心问题：递归参数完全不符合数列定义 #

你的代码里的递归分支完全写错了，根本没有按照Zibonacci的规则拆分输入的num，导致无限递归调用，最终触发栈溢出：

• 对于奇数num≥3，规则是Zib(2n+1) = Zib(n) + Zib(n-1)+1，这里的2n+1就是输入的奇数num，所以应该解出n=(num-1)/2，递归调用的是Zibonacci(n)和Zibonacci(n-1)，而不是你的代码里的Zibonacci(num)（直接调用自身，无限循环）和Zibonacci(num-1)。
• 对于偶数num≥4，规则是Zib(2n) = Zib(n) + Zib(n+1)+1，这里的2n是输入的偶数num，所以n=num/2，递归调用的是Zibonacci(n)和Zibonacci(n+1)，而不是你的代码里的Zibonacci(num)（无限循环）和Zibonacci(num+1)。

修复后的代码示例 #

function Zibonacci(num){
    if(num === 0){
       return 1;
    }
    if(num === 1){
       return 1;
    }
    if(num === 2){
       return 2;
    }
    // 处理奇数≥3的情况：num=2n+1 → n=(num-1)/2
    if(num % 2 !== 0){
       const n = (num - 1) / 2;
       return Zibonacci(n) + Zibonacci(n - 1) + 1;
    }
    // 处理偶数≥4的情况：num=2n → n=num/2
    else {
       const n = num / 2;
       return Zibonacci(n) + Zibonacci(n + 1) + 1;
    }
}

额外优化建议 #

递归版本即使修复后，对于较大的num还是会有重复计算的问题，比如多个分支会重复调用同一个Zibonacci(k)，可以用记忆化缓存来优化性能，避免重复计算：

// 用对象缓存已计算过的结果
const memo = {
    0: 1,
    1: 1,
    2: 2
};

function Zibonacci(num){
    if(memo[num] !== undefined){
        return memo[num];
    }
    let result;
    if(num % 2 !== 0){
       const n = (num - 1) / 2;
       result = Zibonacci(n) + Zibonacci(n - 1) + 1;
    } else {
       const n = num / 2;
       result = Zibonacci(n) + Zibonacci(n + 1) + 1;
    }
    // 缓存结果
    memo[num] = result;
    return result;
}

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