python递归算法（斐波那契数列，汉诺塔、二分法查找）

# 递归算法的三大特点

# 1、递归过程一般通过函数或子过程来实现

# 2、递归算法在函数或子过程的内部，直接或间接调用自己的算法

# 3、递归算法实际上是把问题转换为规模缩小的同类问题的子问题，然后递归调用函数或过程来表示问题的解

# 递归算法要注意的事项

# 1、递归是在过程或函数中调用自身的过程

# 2、递归必须有一个明确的递归结束条件，成为递归出口

# 3、递归算法比较简洁，但运行效率较低

# 4、递归调用过程，系统用栈来存储每一层的返回点和局部量，如果递归次数过多，容易造成栈溢出

# 递归算法的三大特点
# 1、递归过程一般通过函数或子过程来实现
# 2、递归算法在函数或子过程的内部，直接或间接调用自己的算法
# 3、递归算法实际上是把问题转换为规模缩小的同类问题的子问题，然后递归调用函数或过程来表示问题的解
# 递归算法要注意的事项
# 1、递归是在过程或函数中调用自身的过程
# 2、递归必须有一个明确的递归结束条件，成为递归出口
# 3、递归算法比较简洁，但运行效率较低
# 4、递归调用过程，系统用栈来存储每一层的返回点和局部量，如果递归次数过多，容易赵成栈溢出

# 斐波那契数列
fiblist = {}


def fibnum(n):
    if (n <= 1):
        return 1
    if n not in fiblist:
        fiblist[n] = fibnum(n - 1) + fibnum(n - 2)
    return fiblist[n]


def fibrecur(n):
    assert n >= 0, "n > 0"
    if n <= 1:
        return 1
    return fibrecur(n - 1) + fibrecur(n - 2)


def move(n, a, b, c):
    if n == 1:
        print(a, '-->', c)
        return
    else:
        move(n - 1, a, c, b)
        move(1, a, b, c)
        move(n - 1, b, a, c)

def binary_search(alist, item):
    if len(alist) == 0:
        return False
    else:
        midpoint = len(alist)//2
        if alist[midpoint]==item:
            return True
        else:
            if item<alist[midpoint]:
                return binary_search(alist[:midpoint],item)
            else:
                return binary_search(alist[midpoint+1:],item)


def binary_search2(min, max, d, n):
    # min表示有序列表头部索引
    # max表示有序列表尾部索引
    # d表示有序列表
    # n表示需要寻找的元素
    mid = (min + max) // 2
    if max < min:
        print('未找到%s' % d[mid])
    elif d[mid] < n:
        print('向右侧找！')
        binary_search2(mid+1, max, d, n)
    elif d[mid] > n:
        print('向左侧找！')
        binary_search2(min, mid-1, d, n)
    elif d[mid] == n:
        print('索引{0}找到了目标值{1}'.format(mid,n))

if __name__ == '__main__':
    for i in range(0, 20):
        print('loop-', i, fibnum(i))
    for i in range(0, 20):
        print(i, ':', fibrecur(i), end=' ')
        # 1 2 : 2 3 : 3 4 : 5 5 : 8 6 : 13 7 : 21 8 : 34 9 : 55 10 : 89 11 : 144
        # 12 : 233 13 : 377 14 : 610 15 : 987 16 : 1597 17 : 2584 18 : 4181 19 : 6765 89
    print(fibrecur(6))  # 13

    num = 4
    print('把', num, '个盘子全部移到C柱子的顺序为：')
    move(num, 'A', 'B', 'C')

    data = [1, 3, 6, 13, 56, 123, 345, 1024, 3223, 6688]

    print(binary_search(data,3223))
    print(binary_search(data, 3333))

    binary_search2(0, len(data)-1, data, 3223)
    binary_search2(0, len(data)-1, data, 3333)