# -*- coding: utf-8 -*- # recursion function # 递归函数计算 n! = n * (n-1) * ... * 3 * 2 * 1 def factorial(n): if n == 1: return 1 # fact(n) = n * fact(n -1) return n * factorial(n - 1) print('factorial(3) =', factorial(3)) print('factorial(10) =', factorial(10)) # 使用尾递归，优化递归函数的栈溢出 def fact(n): return fact_iter(n, 1) # 要实现尾递归，return 语句不能包含表达式 def fact_iter(num, product): if num == 1: return product # 把每一步的乘积传入到递归函数中 return fact_iter(num - 1, num * product) print('fact(10) =', fact(10)) # 汉诺塔 # a 上面n个盘子，借助b，全部将盘子按同样的顺序放到c上 def move(n, a, b, c): if n == 1: # 最后一步都是 a--> c （这里是a-->c 是形参） print('move:', a, '-->', c) return else: # 将a上面的 n-1个 移到 b （会借助c） move(n-1, a, c, b) # 将a的最下面一个移到c上 move(1, a, b, c) # 将b上的n-1个移到c上 （会借助a） move(n-1, b, a, c) move(4, 'a', 'b', 'c')