有效但意义不大的Return语句

final result: 100
 mult(10, 10)
 {
     makes 100
     mult(20, 5)
     {
         makes 100
         mult(40, 2) + 20
         {
              makes 80
             mult(80, 1)
             {
                   makes 80
                  mult(160, 0) + 80
                  {
                        return 0;
                  }
             }
         }
     }
 }

由于这显然是一个家庭作业问题,我建议你做的协助可能意味着你做。追踪代码。

1) 给出y和z的起始值。 2) 无论是在纸上还是在调试器中,跟踪调用函数时发生的情况。 3) 使用当前y/z值重复步骤2,直到程序完成。

#include <iostream>

using namespace std;

int mult(int y, int z)
{
  if(z==0) {
    cout<<"z is null! - y:"<<y<<" z: "<<z<<endl;
    return 0;
  }
  else if (z%2==1)
  {
    cout<<"z is odd! - y:"<<y<<" z: "<<z<<endl;
    // make z even 
    return mult(2*y,z/2)+y;
  }
  else 
  {
    cout<<"z is even! - y:"<<y<<" z: "<<z<<endl;
    return mult(2*y,z/2);
  }
}


int main()  {

  cout<<"result: "<<mult(3,13)<<endl;

}

输出:

z is odd! - y:3 z: 13
z is even! - y:6 z: 6
z is odd! - y:12 z: 3
z is odd! - y:24 z: 1
z is null! - y:48 z: 0
result: 39

3和13的工作原理:

偶数和奇数之间有一个开关(参见代码中的注释)。

odd: return 0 + 24
odd: return 24 + 12
even: return 36
odd: return 36 + 3 

注意:如果这是家庭作业,请贴上这样的标签。

所以,我们基本上有三个递归的例子。为了更清楚,我将C代码重写为一些函数伪代码。替换 mult (z%2==1) .

你会想出类似的办法

a ** b = 
| b is 0    -> 0 
| b is even -> 2a ** (b/2) 
| b is odd  -> 2a ** (b/2) + a 

你现在明白重点了吗?

一种方法是将每一行翻译成“英语”。我的翻译是这样的:

如果z为零,则返回零

如果z是偶数,则返回mult(y*2,z/2)

注意,这里用z/2调用mult,但是它的参数是整数,所以如果函数继续递归,第二个参数每次都会减半,直到它降到1,最后是1/2,取整到0,此时递归将停止,因为z==0。

有了这些线索,您应该能够理解这个算法是如何工作的。

归纳法的论证是基于证明结果对第一个值是有效的,如果原理对一般值是正确的 N N+1 .

z 在里面 { 0, 1, 2 } 手动测试应该很简单。然后,为了演示归纳步骤,您从一个通用的 z=N mult( y, N ) 是一个有效的结果 mult( y, N+1 ) 不 数字。

y 一

b=下一个奇数(即a+1)

y b=y (a+1)=y*a+y

现在把“a”写成2*(z/2)来迷惑所有人。

y*b变成((2*y)*(z/2))+y

因为偶数和奇数的公式中都出现了“z”,我们认为代码告诉我们(2*y)*(z/2)=(2*y)*(z/2)+y,这显然是疯狂的!

原因是我们偷偷地发现z/2是一个整数,所以z不可能是奇数。当z为奇数时,编译器不允许我们将z/2赋给整数。如果我们试图使“z”为奇数,那么我们真正使用的整数是(z-1)/2,而不是z/2。

a或y

在mult(y,z)中,“y”和“z”都是整数。使用mult(2*y,b/2)上面的符号会变成mult(2*y,a/2),因为编译器会将b/2截断为a/2。

b我们用y

b/2=a/2+1/2,但1/2不能表示为int的一部分。

不是一个真正的答案,但更多的是一个建议。

int mult(int y, int z)
{
  int result = 0;  
  if (z == 0)
    return result;
  result = mult(2 * y, z / 2);  // Common between "then" and "else"
  if ((z % 2) == 1)
  {
     result += y;
  }
  return result;
}

int mult(int y, int z)
{
  int result = 0;  
  if (z != 0)
  {
    result = mult(2 * y, z / 2);  // Common between "then" and "else"
    if ((z % 2) == 1)
    {
       result += y;
    }
  }
  return result;
}

有时简化会增加清晰度。另外,添加注释将帮助您了解自己在做什么,以及下一个阅读代码的人。