随机递归函数是指在递归过程中引入随机选择的递归函数，这类函数虽然单次执行的递归路径可能不同，但在固定随机种子的情况下，其执行过程是确定的，我们可以通过分析内部节点、叶节点来推导其时间复杂度。
随机递归函数的确定性判断
随机递归函数的确定性并不是指每次执行的结果完全一致，而是指在相同的输入和相同的随机种子下，函数的递归路径、执行步骤、返回结果都是固定的。如果没有固定随机种子，每次执行的随机选择不同，递归路径会发生变化，但整体的递归结构仍然遵循预设的规则。
我们可以通过固定随机种子来验证确定性，以下是Python的示例：
import random
def random_recursive(n, seed=None):
# 固定随机种子，保证每次执行逻辑一致
if seed is not None:
random.seed(seed)
# 基线条件，到达叶节点
if n <= 1:
return 1
# 随机选择递归分支，属于内部节点的处理逻辑
choice = random.choice([0, 1])
if choice == 0:
return random_recursive(n-1) + random_recursive(n-2)
else:
return random_recursive(n-2) + random_recursive(n-3)
# 两次使用相同种子调用，结果一致，说明确定性成立
print(random_recursive(5, seed=10))
print(random_recursive(5, seed=10))
内部节点与叶节点的定义
在随机递归函数的递归树模型中，节点分为两类：
- 内部节点：指满足递归条件，会继续调用自身产生子节点的节点，这类节点会执行随机选择逻辑，是递归路径分叉的位置。
- 叶节点：指满足基线条件，不再进行递归调用的节点，这类节点是递归的终止点，不会继续产生子节点。
节点统计示例
以上面的random_recursive函数为例，当输入n=3，固定种子为10时，递归过程如下：
首先n=3是内部节点，随机选择到分支0，调用n=2和n=1；n=2是内部节点，随机选择到分支1，调用n=0和n=-1；n=1、n=0、n=-1都是叶节点，不再递归。
此时内部节点有2个（n=3、n=2），叶节点有3个（n=1、n=0、n=-1）。
时间复杂度分析
随机递归函数的时间复杂度通常和递归树的总节点数相关，总节点数等于内部节点数加叶节点数。由于随机选择的存在，时间复杂度需要取期望值。
期望时间复杂度计算
假设递归函数每次递归有k种等概率的分支选择，每个分支的递归规模分别为n1, n2...nk，基线条件的规模为1，那么期望时间复杂度T(n)满足以下递推式：
T(n) = 1 + (1/k) * (T(n1) + T(n2) + ... + T(nk)) （n>1）
T(1) = 1
我们可以通过代码模拟统计期望时间复杂度，以下是统计n=10时，1000次执行的期望递归调用次数的示例：
import random
def count_recursive(n, seed):
random.seed(seed)
if n <= 1:
return 1 # 叶节点计数
choice = random.choice([0, 1])
if choice == 0:
return 1 + count_recursive(n-1, seed*2) + count_recursive(n-2, seed*2+1)
else:
return 1 + count_recursive(n-2, seed*2) + count_recursive(n-3, seed*2+1)
total = 0
test_times = 1000
for i in range(test_times):
total += count_recursive(10, i)
print("期望递归调用次数：", total / test_times)
通过多次模拟取平均，就可以得到随机递归函数的期望时间复杂度，这种方式比纯数学推导更直观，也适合处理分支逻辑复杂的随机递归场景。