LAB 8 SAMPLE ANSWERS

1.

def main():		
    print sum(10)

def sum(x):
    # Computes the sum from 1 to x, recursively
    if x == 1:
        return 1
    else:
        return x + sum(x-1)

main()

2.

def main():
    value = input("Input which Fibonacci number you want: ")
    print fib(value)

def fib(n):
    if n <= 2:
        return 1
    else:
        x = fib(n-1)
        y = fib(n-2)
        return x+y

main()

Timing:		fib(10) - much less than 1 second
		fib(20) - less than 1 second
		fib(30) - about 2 seconds
		fib(40) - over 1 minute!  

The amount of time it takes to compute fib(n) is the amount of time to 
compute fib(n-1) plus the amount of time to compute fib(n-2). So 
effectively, the amount of time to compute fib(n) approximately doubles
over the amount of time to computer fib(n-1).

3.

def main():
    value = input("Input which positive number you want to analyze: ")
    print size(value)

def size(n):
    if n < 10:
        return 1
    else:
        return 1 + size(n/10)

main()
 
4.

def main():
    A = [7, 4, 6, 9, 2, 8, 1, 50]
    print max(A)

def max(A):
    if len(A)==1:
        return A[0]
    else:
        x = A[0]
        B = A[1:len(A)]
        y = max(B)      # find max of all except first element
        if x >= y:
            return x
        else:
            return y

main()