Recursive multiplication in C

Asked

Viewed 4,551 times

2

I’m learning recursion in C, and I was able to do some programming using recursion. However, I am getting to make a simple program that the user sending two numbers, for example: 6x2, I multiply them in recursion. I can even show the code below, but I’m sure it totally escapes the reality of the real code.

Code:

#include <stdio.h>

int poligono(int n,int v){
    int res=0;

    if(v==0)
        return 0;
    else if(n==0)
        return n;
    else
        return n + poligono(n,v);
}

int main(){

    int n,v,res=0;
    scanf("%d%d",&n,&v);
    res=poligono(n,v);
    printf("Res = %d\n",res);

    return 0;

}
c

  • how to use main as it should be used to see if compiles? Use: int main() { /your code.../ Return 0; }

  • To figure out what’s wrong, take any two numbers and make the hand recursion on a piece of paper. You’ll see your problem.

  • Besides, your code generates infinite recursion, so your code generates an error called (I think you’ve heard of it, rsrs) Stack Overflow. Because it exceeds the limit of "stacked" calls in the stack (stack).

  • Bruno, I apologize, because the code that did not compile was another. This compiles. Soon I will edit my question.

  • @Fiodor does what I told you, takes 2 numbers and runs the function recursively, but keep writing on paper and you’ll understand where your problem is.

  • I’ll take your advice, @Jorgeb.

  • @Fiodor I reversed his question, so that the answers I already had are not invalidated. I warned Math also to edit his answer.

Show 2 more comments

4 answers

2

First, one question that has to be obeyed in recursiveness is that it is finite, that is, there has to be a way out of your program. If you want to do a recursive multiplication, do it this way:

int poligono( int a, int b ){

   if( b == 1)
     return a;
   return a + poligono(a, --b);
}

2

Some points to be improved:

  1. Checking on the first if is unnecessary, you need to treat the n which is the number of times your code is iterated, never the v, which must be a fixed value to be added to itself by n times.
  2. One should never return n, only v.
  3. The value of n shall be decreased with each iteration, or incremented if n is a negative value.
  4. Negative values are not treated in your algorithm.

Putting it all together:

#include <stdio.h>

int poligono(int n, int v){
    int vs;
    if(n>0){
        n--;
        vs = v;
    }
    else if (n<0){
        n++;
        vs = -v;
    }

    if(n==0)
        return vs;
    else
        return vs + poligono(n,v);
}

int main(){

    int n,v,res=0;
    scanf("%d%d",&n,&v);
    res=poligono(n,v);
    printf("Res = %d\n",res);

    return 0;

}

See an example in Ideone: https://ideone.com/XjxKnG

  • originally there was no "n - 1", he edited the question after my comment above,,,

  • That’s right, thank you. However, I was only aware that I had to have a decrease there due to the users above.

  • @Joséx. ah tah, I did not follow the whole history of the evolution of the question, but it was an important point to correct.

  • Math I reversed the question, not to be chameleonic, if you want to edit the answer...

  • @Jorgeb. now that I’ve seen the editing history, is there enough stuff there huh? rs..

1

A recursive algorithm always assumes the use of the same algorithm in a simpler problem, until eventually the problem is so simple that it is no longer necessary to use recursiveness.

In your example, the line return n + poligono(n,v); should be return n + poligono(n-1,v);

Note that I’m not even analyzing whether your program works properly, I’m just solving the problem of infinite recursion.

(I am also assuming that eventually you will put some consistency to avoid using negative values.)

  • I didn’t understand your first sentence, which means that the recursive algorithm should never exist in production?

  • @Math "simplest problem" should actually be "simplest sub-problem"; in this case it is when n== 0; I agree that the text is not very clear, I wrote hastily and then I did not want to edit

  • Ah tah, now I get it. Well, if I edit it I could leave the answer more complete, however I like it there goes my +1

0

The recursive method for multiplying two factors is 3+3+3+3=11: First think about how multiplication is done. 34=11 is the same as 3 + 42 which means the same as 3 + (4*(3-1)) recursively

int poligono(int a , int b) {
        if ((a == 0)||(b==0))
        {
            return 0;
        }
        else {
            return a + poligono(b,(a-1));
        }
    }
  • 1

    3+4*2 is 11, not 12

Browser other questions tagged c

You are not signed in. Login or sign up in order to post.