通过递归伪代码的归纳证明 | 斯基纳算法书

Question

在算法设计手册（第16页）一书中，讨论了以下增量算法的正确性的归纳证明。

Increment(y)
    if (y == 0) return 1;
    else if (y % 2 == 1) return 2 * Increment(floor(y/2));
    else return y + 1;

但我在讨论中的某一点（或假设）感到困惑。请求解决方案（通过归纳证明正确性）以更好地理解。

Answer 1

基本情况 y=0：

通过第一条语句，输出为 0+1 = 1 = y+1；

归纳假设：假设 0 < n < y 增量返回 n+1。

我们试图证明increment(y)返回y+1。

简单的情况，y 是偶数（对于某些 k，y=2k）：

那么y%2为0，if子句为假，返回值为y+1；

奇怪的情况：

假设 y = 2k+1（奇数），则 Floor(y/2) = k，因此：

increment(floor(y/2))=increment(k) = k+1

所以，

2*increment(floor(y/2)) = 2k+2 = y+1

量子电动力学