为何含随机参数的递归函数触发基准情况的次数始终固定？

待分析代码 #

function random(a){
    let i;
    let num=Math.floor((Math.random()*(a+1)))
    return num;
}

function fuc1(n){
    let i;
    if(n<=0){
        alert("condition false ")
        return 0;
    }else{
        i=random(n-1);
        console.log("this\n")
        return fuc1(i)+fuc1(n-1-i);
    }
}

fuc1(6)

问题点 #

我通过alert("condition false ")统计递归终止（返回0）的次数，想辅助分析时间复杂度。但发现尽管递归调用的参数是随机生成的，这个alert却始终执行7次（对应fuc1(6)），对此感到困惑：为什么参数随机的情况下，终止次数完全一致？

原因分析 #

1. 固定终止次数的本质

递归的终止条件是n<=0，每次触发这个条件就会执行alert。我们可以通过数学归纳法证明：调用fuc1(n)时，alert的总次数恒等于n+1，和随机生成的i无关：

• 基础情况：当n=0时，直接触发1次alert，即0+1=1，成立。
• 归纳假设：假设对所有k < n，调用fuc1(k)会触发k+1次alert。
• 归纳步骤：调用fuc1(n)时，会生成随机数i ∈ [0, n-1]，随后递归调用fuc1(i)和fuc1(n-1-i)。根据归纳假设，这两个调用的alert次数分别是i+1和(n-1-i)+1，总和为：

  (i+1) + (n-1-i+1) = n+1
  

  可见无论i取何值，总alert次数都是n+1。对fuc1(6)来说，就是6+1=7次，完全固定。

2. 时间复杂度分析

每次非终止的递归调用都会执行一次console.log("this\n")，结合上面的结论：

• 非终止调用的次数 = 总调用次数 - 终止次数（alert次数）
• 总调用次数 = 终止次数 + 非终止次数 = (n+1) + n = 2n+1（线性级别）

因此，代码的时间复杂度为O(n)，所有操作（递归调用、log输出等）的总次数与n成正比，不受随机参数的影响。

内容的提问来源于stack exchange，提问作者Sahil Kumar Sah