Recursion

1.把问题一点一点剥开
2.注意使用return

#coding:utf-8
#fib
print '------------------fib------------------'
def fib(n):
    if n <= 2:
        return 1
    else:
        return fib(n-1)+fib(n-2)

print '111',[fib(n) for n in range(1,12)]

fib1 = lambda n:1 if n <= 2 else fib1(n-1)+fib1(n-2)

print '222',[fib1(n) for n in range(1,12)]

#reverse a string
print '------------------reverse a string------------------'
def reverse(a):
    if len(a)<=1:
        return a
    else:
        return a[-1]+reverse(a[0:-1])   #string是的时候[]右区间取不到底

s = 'abcde'
print reverse(s)

#二分法用递归
print '------------------二分法------------------'
def erfen(a,b,c):
    i = (a+b)/2
    if (i**2-c) > 1:
        b = i
        return erfen(a,b,c)
    elif (c-i**2) > 1:
        a = i
        return erfen(a,b,c)
    else:
        return i

c = 20.0
a = 0.0
b = 20.0
print erfen(a,b,c)

#二分搜索
print '------------------二分搜索------------------'
def serch(list,key):
    a = len(list)
    if a == 1:
        list.append(key)
        return list
    elif a % 2 != 0:
        if key < list[(a-1)/2]:
            return serch(list[0:(a-1)/2],key)+list[(a-1)/2:]
        else:
            return list[0:(a-1)/2]+serch(list[(a-1)/2:],key)
    else:
        if key < list[a/2]:
            return serch(list[0:(a/2)],key) + list[(a/2):]
        else:
            return list[0:(a/2)] + serch(list[(a/2):],key)

list = [1,2,3,6,7,8,9]
key = 5
print serch(list,key)