Lecture 4: Decomposition and abstraction through functions; introduction to recursion

# example code, Lecture 4, Fall 2008

def sqrt(x):
    ans = 0
    if x >= 0:
        while ans*ans < x: ans = ans + 1
        if ans*ans != x:
            print (x, 'if not a prefect square')
            return None
        else: return ans
    else:
        print(x, 'is a negative number')
        return None

def f(x):
    x = x + 1
    return x

def solve(numLegs, numHeads):
    for numChicks in range(0, numHeads + 1):
        numPigs = numHeads - numChicks
        totLegs = 4*numPigs + 2*numChicks
        if totLegs == numLegs:
            return [numPigs, numChicks]
    return [None, None]

def barnYard():
    heads = int(input('Enter number of heads:'))
    legs = int(input('Enter umber of legs:'))
    pigs, chickens = solve(legs, heads)
    if pigs == None:
        print ('There is no solution')
    else:
        print ('Number of pigs', pigs)
        print ('Number of chickens', chickens)

def solve1(numLegs, numHeads):
    for numSpiders in range(0, numHeads + 1):
        for numChicks in range(0, numHeads - numSpiders + 1):
            numPigs = numHeads - numChicks - numSpiders
            totLegs = 4*numPigs + 2*numChicks + 8*numSpiders
            if totLegs == numLegs:
                return [numPigs, numChicks, numSpiders]
    return [None, None, None]

def barnYard1():
    heads = int(input('Enter number of heads:'))
    legs = int(input('Enter umber of legs:'))
    pigs, chickens, spiders = solve1(legs, heads)
    if pigs == None:
        print ('There is no solution')
    else:
        print ('Number of pigs', pigs)
        print ('Number of chickens', chickens)
        print ('Number of spiders', spiders)

def solve2(numLegs, numHeads):
    solutionFound = False
    for numSpiders in range(0, numHeads + 1):
        for numChicks in range(0, numHeads - numSpiders + 1):
            numPigs = numHeads - numChicks - numSpiders
            totLegs = 4*numPigs + 2*numChicks + 8*numSpiders
            if totLegs == numLegs:
                print ('Number of pigs' + str(numPigs) + '.')
                print ('Number of chickens' + str(numChicks) + '.')
                print ('Number of spiders' + str(numSpiders))
                solutionFound = True
    if not solutionFound: print ('There is no solution')

def isPalindrome(s):
    if len(s) <= 1: return True
    else: return s[0] == s[-1] and isPalindrome(s[1:-1])

def isPalindrome1(s,indent):
    print (indent, 'ispalindrome called with', s)
    if len(s) <= 1:
        print (indent, 'About to return True from base case')
        return True
    else:
        ans = s[0] == s[-1] and isPalindrome1(s[1:-1], indent + indent)
        print (indent, 'About to return', ans)
        return ans

def fib(x):
    if x == 0 or x == 1: return 1
    else: return fib(x-1) + fib(x-2)