how to multiply two positive integers using recursion?-CodePudding

I'm designing a recursive algorithm, in order to create a function that compute product of two positive integers. I'm having problem with the pseudo-code. basic idea:

function definition must be "int Product(int a, int b)",
recursive calls are performed until base case is reached,
each step add "a" to a local variable "result".

the iterative approach works, and it's easy to implement (ignore for a moment the restriction of positive integers, so just consider they are integers. I'll add that condition later):

int Product(int a, int b) {
    int result = 0;
     for (int i = 0; i < b; i  ) {
         result  = a;
    }   return result; 
}

int main(void) {
    int c = Product(3, 2); // 6

    return 0; 
}

now, I've read that if I want to convert from an iterative algortihm in a recursive algorithm all I have to do is rewrite the for-loop in another way:

the checking condition of the for-loop (i.e i < b) is the base case,
the for-loop body (i.e result = a) is the recursive step.

but the problem is that I have no idea how to write that recursive algortihm without using a loop (because if I use a loop I'm not using a recursive approach). And without a loop, it doesn't make sense to create the local variable "i" as a counter, because I can't use goto command to jump backward.

CodePudding user response：

A for-loop schema as:

func() {
    for (int i=0; i<N; i  ) {
       body
    }
}

can be rewritten as the following recursive schema:

for_func(int i) {
    if (i<N) { body; for_func(i 1); }
    return;
}

Then you can rewrite:

int Product(int a, int b) {
    int result = 0;
     for (int i = 0; i < b; i  ) {
         result  = a;
    }
    return result; 
}

as:

int rec_Product(int result, int i, int a, int b) {
    if (i<b) {
        return Product(result a,i 1,a,b);
    } else {
        return result;
    }
}

int Product(int a, int b) {
    return rec_Product(0,0,a,b);
}

CodePudding user response：

What you're doing here isn't a recursive function due to your for-loop in the function. You'd need to implement it as follows:

#include <stdio.h>

int product(int prod, int amount) {
    if (amount == 0)
        return 0;

    return prod   product(prod, amount - 1);
}

int main() {

    int c = product(2, 3);

    return 0;
}

CodePudding user response：

What you have described is a general approach of converting an iterative function to a recursive function.

However recursive functions can have their own specificity.

For example it is desirable to decrease the number of recursive calls to avoid stack overflow.

Introducing intermediate variables can be redundant.

As for your function than its parameters should have the unsigned integer type unsigned int. Otherwise the function can have undefined behavior.

The return type of the function should be unsigned long long to avoid the overflow of the production of bigs numbers. For example if you will call your function when the first argument is equal to INT_MAX and the second argument is equal to 2 then your function will return an invalid result.

Taking all this into account the function can be defined the following way

#include <stdio.h>

unsigned long long int product( unsigned int a, unsigned int b )
{
    return b == 0 ? 0 : a   product( a, ( b - 1 ) / 2 )   product( a, b - 1 - ( b - 1 ) / 2 );
}

int main( void )
{
    unsigned int a = 2;
    for (unsigned int b = 0; b < 11; b  )
    {
        printf( "%llu ", product( a, b ) );
    }
    putchar( '\n' );
}

The program output is

0 2 4 6 8 10 12 14 16 18 20

The idea of the function is based on this relation: if b is equal to n1 n2 then a * b is equal to a * ( n1 n2 ) that is equal to a *n1 a * n2. That is you can decrease the number of levels of recursive calls of the functions.

The return statement of the function can be also written like

return b == 0 ? 0 : ( --b, a   product( a, b / 2 )   product( a, b - b / 2 ) );