Min # of Coins, ternary tree

Given an amount of cents, what is the minimum number of coins needed to get the amount? 

Version #1
# coin.py
# preorder: root, left (25), mid (10), right (9)

total = 30
totalCoin = 0
minCoin = 100

def preorder(leftOver, direction):
    global totalCoin
    global minCoin

    print ("minCoin ", minCoin, " : totalCoin ", totalCoin, " : leftOver ", leftOver, " : direction ", direction)

    if (leftOver > 0):
        totalCoin +=1
        preorder(leftOver - 25, 1)
        preorder(leftOver - 10, 0)
        preorder(leftOver - 1, -1)
    else:
        if (leftOver == 0):
            if (minCoin > totalCoin):
                minCoin = totalCoin

    if (direction == -1):
        totalCoin -= 1

    return

preorder(total, 1)

Version #2: prevent from going back to left if mid/right
# coin.py
# root, left (25), mid (10), right (9)
# preorder: root, left, mid, right

total = 30
totalCoin = 0
minCoin = 100

def preorder(leftOver, direction):
    global totalCoin
    global minCoin

    print ("minCoin ", minCoin, " : totalCoin ", totalCoin, " : leftOver ", leftOver, " : direction ", direction)

    if (leftOver > 0):
        totalCoin +=1
        if (direction > 0) : 
            preorder(leftOver - 25, 1)

        if (direction > -1) :
            preorder(leftOver - 10, 0)

        preorder(leftOver - 1, -1)
    else:
        if (leftOver == 0):
            if (minCoin > totalCoin):
                minCoin = totalCoin

    if (direction == -1):
        totalCoin -= 1

    return

preorder(total, 1)

Version #3: stop early
# coin.py
# root, left (25), mid (10), right (9)
# preorder: root, left, mid, right

total = 30
totalCoin = 0
minCoin = 100

def preorder(leftOver, direction):
    global totalCoin
    global minCoin

    print ("minCoin ", minCoin, " : totalCoin ", totalCoin, " : leftOver ", leftOver, " : direction ", direction)

    if (totalCoin < minCoin):
        if (leftOver > 0):
            totalCoin +=1
            if (direction > 0) :
                preorder(leftOver - 25, 1)

            if (direction > -1) :
                preorder(leftOver - 10, 0)

            preorder(leftOver - 1, -1)
        else:
            if (leftOver == 0):
                if (minCoin > totalCoin):
                    minCoin = totalCoin

    if (direction == -1):
        totalCoin -= 1

    return

preorder(total, 1)