如何找到递归方程（对于这个伪代码）？

Question

我的任务是寻找以下问题的答案，但老实说，我完全不知道从哪里开始。我不是在寻找每个人说的直接答案（尽管他们会很感激），而是我如何 find/derive 他们。递归我懂，就是不明白递归方程怎么找

a.) 给出随机的预期运行时间的重复。

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

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

伪代码：

Function RANDOM(u)

if u = 1 then

return(1)

else

   assign x=0 with probability 1/2, or

   assign x=1 with probability 1/3, or

   assign x=2 with probability 1/6

if x=0 then

return(RANDOM(u-1) + RANDOM(u-2))

   end-if

if x=1 then

return(RANDOM(u) + 2*RANDOM(u-1))

end-if

   if x=2 then

return(3*RANDOM(u) + RANDOM(u) + 3)

end-if

end-if

end-RANDOM

Answer 1

首先需要注意的是，因为问题要求 运行时间 / 没有。调用，对RANDOM的递归调用前面的系数无关紧要（因为none的答案取决于实际的return值）。

此外，由于问题询问的是预期数量，您可以根据概率混合适当的递归调用。

a)

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

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。我会把它留给你，因为它是微不足道的。

如何找到递归方程（对于这个伪代码）？

How does one find a recurrence equation (for this pseudocode)?

recursion

equation

equation-solving