Too many recursions at a time-CodePudding

I want to create a program that determines whether or not it is possible to construct a particular total using a speciﬁc number of coins using recursion. For example, it is possible to have a total of $1.00 using four coins if they are all quarters. However, there is no way to have a total of $1.00 using 5 coins. Yet it is possible to have $1.00 using 6 coins by using 3 quarters, 2 dimes and a nickel. Similarly, a total of $1.25 can be formed using 5 coins or 8 coins, but a total of $1.25 can not be formed using 4, 6 or 7 coins. It should display a clear message indicating whether or not the entered dollar amount can be formed using the number of coins indicated

def possiblechange(total, coins):
    penny = .01
    nickel = .05
    dime = .1
    quarter = .25
    if coins * penny == total:
        return True
    elif nickel * coins == total:
        return True
    elif dime * coins == total:
        return True
    elif quarter * coins == total:
        return True
    else:
        return (
            penny*possiblechange(total, coins) or 
            nickel*possiblechange(total, coins) or 
            dime*possiblechange(total, coins) or
            quarter*possiblechange(total, coins)
        )
print(possiblechange(1.0, 3))

I get a traceback on this.

CodePudding user response：

You've got a few issues.

The big one is that your code recurses with the exact same arguments every time. That means that if the initial call is not handled by one of your base cases, you'll recurse forever. You need to be modifying the arguments to the recursive calls, so they're doing something different than you're doing in the current call.

Actually, your recursive case don't make any sense at all. Your function is supposed to return True or False, but you're doing math on a bunch of dollar values instead there.

I think you want something like this for your recursive case:

return (
    possiblechange(total-penny, coins-1) or
    possiblechange(total-nickel, coins-1) or
    possiblechange(total-dime, coins-1) or
    possiblechange(total-quarter, coins-1)
)

The next issue is that you don't have any base case to handle failure. If you can't find a working set of change, you need to return False. I'd suggest:

if total < 0 or coins == 0:
    return False

The final issue is a subtle one. You're doing your mathematics with floating point numbers, which may not work exactly. You should probably work in cents, instead of fractions of a dollar, so that every denomination can be exactly represented.

CodePudding user response：

You have to subtract the total and coins from each recursive call. Also what is the point in multiplying the value of the coin by the boolean result? For example, instead of quarter*possiblechange(total, coins) do possiblechange(total - querter, coins - 1) .

CodePudding user response：

The python recursion limit is set to 1000. However, if your computer has enough resources, you can increase this limit by putting this code in the very first line:

import sys
sys.setrecursionlimit([NUMBER OF RECURSIONS])

Replace [NUMBER OF RECURSIONS] with the number of recursions you need.

IMPORTANT: Your function does return booleans AND numbers. Please mind that Python treats booleans as numbers in operations: True means 1 and False 0. This might be the problem directing your function in way more recursions than needed.