# !/usr/bin/env python3
# -*- coding: utf-8 -*-

''' 
在函数内部，可以调用其它函数，如果一个函数在内部调用自身本身，这个函数就是递归函数
'''
# 举例，计算阶乘 n! = 1 * 2 * 3 * ... * n，用函数 fact(n) 表示，可以看出

''' 
fact(n) = n!
        = 1 * 2 * 3 * ... * (n-1) * n
        = (n-1)! * n
        = fact(n-1) * n

所以， fact(n) 可以表示为 n*fact(n-1),只有 n=1时需要特殊处理
'''
# 于是，fact(n)用递归的方式写出来就是：
def fact(n):
    if n==1:
        return 1
    return n * fact(n-1)

fact(1)

fact(2)

fact(8)

fact(100)


''' 
使用递归函数需要注意防止栈溢出。在计算机中，函数调用是通过栈(stack)这种数据结构实现的，每当进入一个函数调用，栈就会加一层栈帧，每当函数返回，栈就会减一层栈帧，
由于栈的大小不是无限的，所以递归调用的次数过多，会导致栈溢出
'''

fact(1000)
# RecursionError（超过递归深度限制）: maximum recursion depth exceeded in comparison(递归的次数超过了最大的深度 简称递归溢出)

''' 
解决递归调用栈溢出的方法是通过尾递归优化，事实上尾递归和循环的效果是一样的，所以，把循环看成是一种特殊的尾递归函数也是可以的。
尾递归是指，在函数返回的时候，调用自身本身，并且，return语句不能包含表达式，这样编译器或者解释器就可以吧尾递归做优化，使递归本身无论调用多少次，都只占用一个栈帧，不会出现栈溢出的情况。
上面的fact(n)函数由于return n * fact(n-1)引入了乘法表达式，所以就不是尾递归了。要改成尾递归方式，需要多一点代码，主要是要把每一步的乘积传入到递归函数中：
'''
def facr(n):
    return fact_iter(n, 1)

def fact_iter(num, product):
    if num == 1:
        return product
    return fact_iter(num -1, num*product)

''' 
可以看到，return fact_iter(num-1, num*product)仅返回递归函数本身，num-1 和 num*product在函数调用前就会被计算，不影响函数调用
'''

fact(2)

fact(5)

# fact(5) 对应的  fact_iter(5, 1)的调用如下：
# ---fact_iter(5, 1)
# ---fact_iter(4, 5)
# ---fact_iter(3, 20)
# ---fact_iter(2, 60)
# ---fact_iter(1, 120)

fact(1000)

''' 
尾递归调用时，如果做了优化，栈不会增长，因此，无论多少次调用也不会导致栈溢出。
遗憾的是，大多数编程语言没有针对尾递归做优化，Python解释器也没有做优化，所以，即使把上面的fact(n)函数改成递归方式，也会导致栈溢出。
'''

#** 小结
''' 
使用递归函数的优点是逻辑简单清晰，缺点是过深的调用会导致栈溢出。
针对尾递归优化的语言可以通过尾递归防止栈溢出。尾递归事实上和循环是等价的，没有循环语句的编程语言只能通过尾递归实现循环。
Python标准的解释器没有针对尾递归做优化，任何递归函数都存在栈溢出的问题。
'''

#** 练习
''' 
汉诺塔的移动可以用递归函数非常简单地实现
请编写move(n, a, b, c)函数，它接受参数n，表示3个柱子A、B、C中第1个柱子A的盘子数量，然后打印出所有盘子从A借助B移动到C的方法
'''
# 思考
# 分三步
# 1、把n-1个盘子先a搬到b
# 2、把n(最底下的盘子)a搬到c
# 3、把n-1个盘子从b搬到c

def move(n, a, b, c):
    if n == 1:
        print(a,'-->',c)
    else:
        move(n - 1, a, c, b)
        print(a,'-->',c)
        # move(n, a, b, c)
        # print(a,'-->',c)
        move(n - 1, b, a, c)
        # print(b,'-->',c)
        
move(3, 'A', 'B', 'C')





