伪代码递归函数

Question

我正在为期中考试而学习，其中一个练习题要求：

考虑递归伪算法Milk（a），该算法将a> = 1作为输入整数。

MILK(a)
    if a = 1;
    then eat cookie;
    else drink glass of milk;
       select a random integer b with 1 <= b <= a-1
       MILK(b);
       MILK(a-b);
    endif

1）解释为什么对于任何整数a> = 1算法，MILK（a）终止

我认为因为n-1，对于递归函数MILK（b）的输入，m的可能性变得越来越小，最终达到满足条件a = 1的1；因此吃了一个cookie，因此终止了算法。

2）令M（a）为您在运行MILK（a）时喝的牛奶量。确定M（a）的确切值

对于这个，我假设它将是M（a）= a + a，因为每次您运行它时，输入都是“ a”，将每个输入相加即可得出总数。

我的答案如何？或者这完全不正确。谢谢！

Answer 1

第一个答案很好。

然而，第二个却不是。考虑a=1。您的答案是两杯或牛奶，而正确答案是零。提示：尝试手动完成一些小示例，以了解算法中发生的情况。