如何找到递归方程(对于此伪代码)?

Question

我的任务是找到以下问题的答案，但老实说，我完全不知道从哪里开始。我不是在寻求每个说法的直接答案(尽管他们会不胜感激(，而是我如何找到/推导它们。我理解递归，我只是不明白如何找到递归方程。

a.(给出 RANDOM 的预期运行时间的重复周期。

b.(给出调用 RANDOM(n( 执行的递归调用的预期递归次数的确切递归方程。

c.(给出第 14 行重新运行语句执行的预期次数的确切递归方程，在所有调用 RANDOM(n( 时，递归与否。

伪代码：

函数随机(u(

1. 如果你 = 1，那么

2.   返回(1(

3. 还

4.    分配 x=0，概率为 1/2，或

5.    分配 x=1，概率为 1/3，或

6.    分配 x=2，概率为 1/6

7.    如果 x=0，则

8.       返回(随机(U-1( + 随机(U-2((

9.    结束-如果

10.    如果 x=1，则

11.       返回(随机(U( + 2*随机(U-1((

12.    结束-如果

13.    如果 x=2，则

14.       返回(3*随机(U( + 随机(U( + 3(

15.    结束-如果

16. 结束-如果

结束随机

Answer 1

首先，重要的是要注意，由于问题要求运行时/否。 调用，递归RANDOM调用前面的系数无关紧要(因为没有一个答案取决于实际的返回值(。

此外，由于问题要求预期数量，因此您可以概率地混合适当的递归调用。

---

一(

开始很容易。函数的概率混合：

T(u) = [1/2] * [T(u-1) + T(u-2)] + 
[1/3] * [T(u)   + T(u-1)] + 
[1/6] * [T(u)   + T(u)  ]        // + constant amount of work

b(

和以前一样，但请记住为每个呼叫添加一个：

N(u) = [1/2] * [N(u-1) + N(u-2) + 2] +
[1/3] * [N(u)   + N(u-1) + 2] +
[1/6] * [N(u)   + N(u)   + 2]    // no constants here

c(

这比其他两个更棘手。这个问题要求"[所有对 RANDOM(u(] 的调用，无论是否递归"，但只有第 14 行上的那些是递归的......

无论如何，忽略这个小细节，需要注意的关键是，对第 11 行RANDOM(u)的调用也可以产生所需的递归调用，而不会对总数本身产生影响。改编上述内容：

R(u) = [1/3] * [R(u)           ] +     // don't add 1 here
[1/6] * [R(u) + R(u) + 2]       // add 2 as before

---

请注意，该问题可能希望您将所有T(u), N(u), R(u)术语重新排列到 LHS。我会把它留给你，因为它是微不足道的。