Return statement that works but doesn't make much sense

Question

I have the following function:

int mult(int y, int z)
{
  if (z == 0)
    return 0;
  else if (z % 2 == 1)
    return mult(2 * y, z / 2) + y;
  else 
    return mult(2 * y, z / 2);
}

What I need to do is prove its correctness by induction. Now the trouble I'm having is that even though I know it works since I ran it I can't follow each individual step.

What is confusing me is that y only shows up as an argument and in no place does it show up in a return except in the recursive part, and yet the function actually returns y as the answer.

How does this happen? I need to be able to follow everything that happens so that I can do the iterations of it for the proof.

Answer 1

One approach would be to translate each line into "English". My translation would be something like this:

if z is zero, return zero
if z is odd, return mult(y*2, z/2) + y
if z is even, return mult(y*2, z/2)

The general pattern is to recursively call mult with the first parameter doubling, and the second parameter halving.

Note that here you're calling mult with z/2, but its arguments are integers, so if your function continues to recurse, the 2nd parameter will halve each time until it gets down to 1, and then finally 1/2 which rounds down to 0 - at which point recursion will stop because z==0.

With those clues, you should be able to understand how this algorithm works.

Answer 2

Not really an answer, but more of a suggestion.
You may want to reduce the recursion call from 2 to one:

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;
}

This could be simplified once more by observing the rule "one exit point only":

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;
}

Although many compilers will perform this simplification automatically, debugging is usually easier when the code is simplified. The debugger will match the code when single-stepping.

Sometimes simplifying will add clarity. Also, adding comments will help you figure out what you are doing as well as the next person who reads the code.

Answer 3

ya = ya

a = an even number

b = the next odd number (in other words a + 1)

So, if you want the equation above in terms of only even numbers (an 'a') when given an odd number (a 'b') you can do the following:

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

Now confuse everyone by writing 'a' as 2*(z/2).

y*a becomes (2*y)*(z/2)

y*b becomes ((2*y)*(z/2))+y

Since 'z' appears in the formula for both even and odd numbers, we want to think that the code is telling us that (2*y)*(z/2) = (2*y)*(z/2) + y which is obviously MADNESS!

The reason is that we have snuck in the fact that z/2 is an integer and so z can never be odd. The compiler will not let us assign z/2 to an integer when z is odd. If we try to make 'z' odd, the integer we will really be using is (z-1)/2 instead of z/2.

To get around this, we have to test to see if z/2 is odd and pick our formula based on that (eg. either ya or yb in terms of 'a').

In mult(y,z) both 'y' and 'z' are both integers. Using the symbols above mult(2*y,b/2) becomes mult(2*y,a/2) because b/2 will be truncated to a/2 by the compiler.

Since we are always going to get an 'a' as a parameter to 'mult', even when we send a 'b', we have to make sure we are only using formulas that require 'a'. So, instead of yb we use ya+1 as described above.

b/2 = a/2 + 1/2 but 1/2 cannot be represented as part of an int.

Answer 4

Demonstrations by induction are based on proving that the result is valid for the first value, and that if the principle is correct for a generic value N, it is provable that it holds for N+1.

To simplify, you can start by proving that it works for z in { 0, 1, 2 } which should be trivial with a manual test. Then to demonstrate the induction step, you start with a generic z=N, and prove that if mult( y, N ) is a valid result, then mult( y, N+1 ) is also a valid result in terms of the previous one. Since there are different branches for even and odd numbers, you will have to prove the induction step for both even and odd N numbers.

Answer 5

#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;

}

Output:

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

How it works for 3 and 13:

There's a switch for even and odd numbers (see comment in code).

When z is null, the recursion "starts to return to the initial call". If the number z is odd it adds y to the returned value of the recursive call, if it's even it justs returns the value from the recursive call.

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

Answer 6

Since this is obviously a homework question, I recommend you do what the assinment was likely meant fot you to do. Trace through the code.

1) give a starting value for y and z. 2) either on paper or in a debugger, trace what happens when you call the function. 3) repeat step 2 with your current y/z values until program completion.

Answer 7

step-by-step analisis

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;
                  }
             }
         }
     }
 }

Answer 8

Note: If this is homework, tag it as such.

So, we basically got three recursive cases. To make it all clearer, I'd rewrite the C-code into some functional pseudo-code. Replace mult with an intuitive operator sign and figure out descriptive explanations of low-level expressions like (z%2==1).

You'll come up with something like

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

Do you get the point now?