CODEWITHSUNDEEP
pythonpython-3.xrecursion
user8822765
user8822765

Reputation:

Multiplication using only recursion

Hey I'm trying to write some code that doesn't use any of the normal python code for multiplication, division or loops. Right now im trying to do the multiplication part. Here's what i have so far.

def incr(a):
'''Returns the next integer after a'''
return a + 1

def zero(a):
'''Returns True if a is zero'''
return a == 0

def decr(a):
'''Returns the integer before a'''
return a -1

def add(a, b):
    '''Returns the sum of a and b'''
    # using only incr, decr, zero, and recursion

    a = incr(a)

    b = decr(b)

    if zero(b) != 1:
        add(a,b)

    if zero(b) != 0:
        print(a)

    #return 0
    return a #edit

def mult(a, b):
     '''Returns the product of a and b'''
     # using only add, incr, decr, zero, and recursion

    add(a,a)

    b= decr(b)

    if zero(b) != 0:
        mult(a,b)

    if zero(b) != 0:
        print(a)

    #return 0
    return a #edit

 mult(2,4)

However, the code for the mult() is only adding, not multiplying. for this I should be getting 8,but I'm only getting 4. So for some reason it's not running the script again.

Upvotes: 0

Views: 1523

Answers (4)

Blckknght
Blckknght

Reputation: 104712

Integers in Python are immutable. That means you can't modify them in place, only rebind a variable in the current scope to a new integer. This means you need to use the return values of things like incr and decr, and you need to write your add and mult functions to return their results too.

Currently your code ignores the results of the recursive calls to add and mult and unconditionally returns 0 at the end of each function. That's always going to do the wrong thing.

I think you want something more like this:

def add(a, b):
    '''Returns the sum of a and b'''
    # using only incr, decr, zero, and recursion

    if zero(b):
        return a

    a = incr(a)
    b = decr(b)
    return add(a,b)

def mult(a, b):
    '''Returns the product of a and b'''
    # using only add, incr, decr, zero, and recursion

    if zero(b):
        return 0

    b = decr(b)
    c = mult(a, b)
    return add(a, c)

Both of these should work for any integer a and any non-negative integer b. If you want to support negative b values, you'd need new "primitive" functions (e.g. a sign function, perhaps).

Upvotes: 1

spitfire21
spitfire21

Reputation: 103

You are going to run into some issues with what your are doing in mult because mult does not actually modify the variable a. What you are doing in add is creating lots of copies of a and b and printing when b == 0. This will not work for mult because you are not setting a to the result of add. You will need to have a recursive function that returns a value. For example:

def mult(a, b):
    if b == 0:
         return 0
    b= b-1
    temp=0
    temp += a



    if b != 0:
        temp += mult(a,b)

    return temp

print(mult(8,8))

Read about pass by reference and pass by value in Python

Edit**

def add(a, b):
'''Returns the sum of a and b'''
# using only incr, decr, zero, and recursion


if b != 0:
    a = incr(a)
    b = decr(b)
    a = add(a,b)

return a


def mult(a, b):
    temp = 0  
    if b == 0:
        return 0
    temp = add(a,temp)
    b = decr(b)
    if b != 0:
        temp = add(mult(a,b),temp)

    return temp

Upvotes: -1

wwii
wwii

Reputation: 23753

To multiply a and b, you need to add a to itself b times. For a recursive function that takes a and b for arguments: each function call will add a to the result of the recursive call; and on each recursive call 'b' is decremented; the recursion stops when b is zero.

def mult(a, b):
    '''Returns the product of a and b'''
    # using only add, incr, decr, zero, and recursion

    #base case
    if zero(b):
        return 0
    # a + (a + (a + ... + (0)...))
    return add(a, mult(a, decr(b)))

One thing you missed in your solution that is key to recursion is that the function needs to return a result to the function that called it.

Upvotes: 1

user8502296
user8502296

Reputation:

You just have your logic messed up in your mult function.

   if zero(b) != 0

This evaluates to false when b is not 0. This is preventing mult from being called again.

You really don't need to specify if zero(b) != 0 since that is just equating a boolean to a boolean.

if !zero(b) would do the exact same thing and be easier to understand.

Upvotes: 0

Related Questions