I can multiply two numbers without using multiplication operator in c. I know that in recursion we call function inside function. I don't understand the recursion method for multiplying two numbers.

#include<stdio.h>

int main()
{
    int x = 2;
    int y = 4;
    int mul = 0;
    
    // x = 0 + 2 = 2
    // x = 2 + 2 = 4
    // x = 4 + 2 = 6
    // x = 6 + 2 = 8
    
    for (int i = 0; i < y; i++)
    {
        mul = (mul + x);
    }
    
    printf("%d", mul);
    
    return 0;
}

https://www.geeksforgeeks.org/multi...iply-division-bitwise-operators-and-no-loops/

can someone explain math for multiplying two numbers using recursion ?

 

Multiplication is just a shorthand for repeated addition of a number to itself a prescribed number of times. Similarly, division can be decomposed into repeated subtractions.

As a side note, the code fragment is NOT an example of a recursive procedure. It is just a simple looping construct. Recursion would invove repeated calls by a function to itself. Computing factorials in this manner is a classic example.

Here is the pseudo code for it:

fac ≔ proc(n) local s;
if n=0 then s≔ 1 else s≔ n*fac(n-1) end if;
return s;
end proc:

Notice how the function calls itself in the else part of the conditional 'if' statement. Each call results in a completely new stack frame for the function and when the top level return is executed the value return will be the required answer.

 

But...your looping structure is the right idea for multiplication. Have you tested it yet?

 

I can multiply two numbers without using multiplication operator in c. I know that in recursion we call function inside function. I don't understand the recursion method for multiplying two numbers.

#include<stdio.h>

int main()
{
    int x = 2;
    int y = 4;
    int mul = 0;
   
    // x = 0 + 2 = 2
    // x = 2 + 2 = 4
    // x = 4 + 2 = 6
    // x = 6 + 2 = 8
   
    for (int i = 0; i < y; i++)
    {
        mul = (mul + x);
    }
   
    printf("%d", mul);
   
    return 0;
}

https://www.geeksforgeeks.org/multi...iply-division-bitwise-operators-and-no-loops/

can someone explain math for multiplying two numbers using recursion ?

Your code does not scale well to large numbers. The number of times that your loop executes is equal to y. If you use your loop to multiply two two-digit numbers together, it will take a certain amount of time. If you then use it to multiply two three-digit numbers together, it will take, on average, ten times as long. By the time you get to multiplying two ten-digit numbers together, it is taking a billion times as long. Now consider how long it takes a human to multiply two ten-digit numbers together compared to two two-digit numbers -- perhaps fifty times as long. Ask a human to multiply two 20-digit numbers together, and they'll slog it out in about half an hour, while your program will likely take several thousand years.

As for the recursive approach, which is a REALLY poor use of recursion, the underlying math is simple.

z = x*y = x(1 + y - 1) = x*1 + x*(y-1) = x + x*(y-1)

When do you stop?

If y = 0, the result is simply 0.

This approach requires that y be a non-negative integer. We can relax the non-negative requirement by noting that x*y = -x(-y) and use that as our first check to get the ball rolling with a non-negative y.

As for dealing with non-integer values -- that's a completely different problem. The notion that multiplication is repeated addition runs into difficult when asked to multiply x by itself 3.872 times.

 

I can multiply two numbers without using multiplication operator in c. I know that in recursion we call function inside function. I don't understand the recursion method for multiplying two numbers.

#include<stdio.h>

int main()
{
    int x = 2;
    int y = 4;
    int mul = 0;

    // x = 0 + 2 = 2
    // x = 2 + 2 = 4
    // x = 4 + 2 = 6
    // x = 6 + 2 = 8

    for (int i = 0; i < y; i++)
    {
        mul = (mul + x);
    }

    printf("%d", mul);

    return 0;
}

https://www.geeksforgeeks.org/multi...iply-division-bitwise-operators-and-no-loops/

can someone explain math for multiplying two numbers using recursion ?

How big can the numbers get? A 2D array will work, just populate it with the products of integer pairs and you're done. You can save space too by recognizing that 2*3 is the same as 3*2 and so on. This approach has constant cost too, 3*4 is "computed" in the time same as 234*75.

 

How big can the numbers get? A 2D array will work, just populate it with the products of integer pairs and you're done. You can save space too by recognizing that 2*3 is the same as 3*2 and so on. This approach has constant cost too, 3*4 is "computed" in the time same as 234*75.

This approach becomes untenable long before the loop approach does. Just to deal with 16-bit x 16-bit numbers would result in an 8 GB table, even after exploiting symmetry.

 

This approach becomes untenable long before the loop approach does. Just to deal with 16-bit x 16-bit numbers would result in an 8 GB table, even after exploiting symmetry.

Indeed, I asked about the desired range too. I thought it helpful to show the OP there are often unconventional ways to look at these kinds of problem.