递归和字典

#iterarion
def factorial_iter(n):
    prod = 1
    for i in range(1, n+1):
        prod *= i
        return prod

#recursion
def factorial(n):
    if n == 1:
        return 1
    else:
        return n * facturial(n-1)

#从程序员的角度上，递归更简洁，因为不需要定义内置变量。而从计算机角度，迭代效率更高。
#另一个列子，把乘法用加法的形式体现

def mult_iter(a, b):
    result = 0
    while b > 0:
        result += a
        b -= 1
    resurn result

def mult(a, b):
    if b == 1:
        return a
    else:
        return a + mult(a, b-1)

#递归方式解决斐波那契数列
    
def fib(n):
    if n == 0 or n == 1:
        return 1
    else:
        return fib(n - 1) + fib(n - 2)

#用字典高效解决斐波那契数列的递归运算量问题，避免因递归造成的数值重复计算，

def fib_efficient(n):
    d = {0:1, 1:1}
    if n in d:
        return d[n]
    else:
        return fib(n-1) + fib(n-2)

print(fib_efficient(10))

#递归方式解决回文问题

def isPalindrome(s):
    def toChars(s):
        s = s.lower()#将字符串转化为小写字母
        ans = ""
        for char in s:
            if char in "abcdefghigklmnopqrstuvwxyz":
                ans += char #将字符中的字母抽离出来
        return ans

    def isPal(s):
        if len(s) == 1:
            return True
        else:
            return s[0] == s[-1] and isPal(s[1:-1]) #将s[1:-1]作为新的参数输入isPal()函数

    return isPal(toChars(s)) #调用isPal()函数来处理经过toChars()输出的文字

总结，递归就是把一个大问题，转化为比他小一点的问题，然后再转化为比他小一点的问题的小一点的问题，最终小到一个已知的答案，这个答案也是递归停止的条件。