How to multiply without the * sign using recursion?

Question

so as homework for a programming class on python we're supposed to multiply to integers (n,m) with each other WITHOUT using the * sign (or another multiplication form). We're supposed to use recursion to solve this problem, so i tried just adding n with itself, m number of times. I think my problem is with using recursion itself. I have searched on the internet for recursion usage, no results. Here is my code. Could someone point me in the right direction?

    def mult(n,m):
        """ mult outputs the product of two integers n and m
            input: any numbers
        """
        if m > 0:
            return n + n 
            return m - 1
        else:
            return 1

hint: usually, recursion involves a function calling _itself_ in at least one of the code-paths. — mgilson, Sep 19 '16 at 16:36
Try to define multiplication in terms of a base case and the recursive case. The base case is *zero*, not 1, because 0 times anything is always 0. The recursive case is `n + mult(n, m - 1)`, so `n` added to the multiplication of `n` and `m` minus 1. — Martijn Pieters, Sep 19 '16 at 16:36
Take a look at [Building a recursive function in Python](http://stackoverflow.com/questions/479343/how-can-i-build-a-recursive-function-in-python) or its linked question [basics of recursion in Python](http://stackoverflow.com/questions/30214531/basics-of-recursion-in-python) — LinkBerest, Sep 19 '16 at 16:38
Another potentially useful resource: http://www.python-course.eu/recursive_functions.php — Liesmith, Sep 19 '16 at 16:39

score 1 · Answer 1 · answered Sep 19 '16 at 16:50

I don't want to give you the answer to your homework here so instead hopefully I can provide an example of recursion that may help you along :-).

# Here we define a normal function in python
def count_down(val):
    # Next we do some logic, in this case print the value
    print(val)

    # Now we check for some kind of "exit" condition. In our
    # case we want the value to be greater than 1. If our value 
    # is less than one we do nothing, otherwise we call ourself
    # with a new, different value.
    if val > 1:
        count_down(val-1)

count_down(5)

How can you apply this to what you're currently working on? Maybe, instead of printing something you could have it return something instead...

score 1 · Answer 2 · answered Sep 19 '16 at 17:47

Thanks guys, i figured it out!!! i had to return 0 instead of 1, otherwise the answer would always be one higher than what we wanted. and i understand how you have to call upon the function, which is the main thing i missed. Here's what i did:

    def mult(n,m):
        """ mult outputs the product of two integers n and m
            input: any numbers
        """
        if m == 0:
            return 0
        else:
            return n + mult(n, m - 1)

score 0 · Answer 3 · answered Sep 19 '16 at 17:44

You have the right mechanics, but you haven't internalized the basics you found in your searches. A recursive function usually breaks down to two cases:

Base Case -- How do you know when you're done? What do you want to do at that point?

Here, you've figured out that your base case is when the multiplier is 0. What do you want to return at this point? Remember, you're doing this as an additive process: I believe you want the additive identity element 0, not the multiplicative 1.

Recursion Case -- Do something trivial to simplify the problem, then recur with this simplified version.

Here, you've figured out that you want to enhance the running sum and reduce the multiplier by 1. However, you haven't called your function again. You haven't properly enhanced any sort of accumulative sum; you've doubled the multiplicand. Also, you're getting confused about recursion: return is to go back to whatever called this function. For recursion, you'll want something like

mult(n, m-1)

Now remember that this is a function: it returns a value. Now, what do you need to do with this value? For instance, if you're trying to compute 4*3, the statement above will give you the value of 4*2, What do you do with that, so that you can return the correct value of 4*3 to whatever called this instance? You'll want something like

result = mult(n, m-1)
return [...] result

... where you have to fill in that [...] spot. If you want, you can combine these into a single line of code; I'm just trying to make it easier for you.

How to multiply without the * sign using recursion?

3 Answers3