Python学习笔记 | 递归函数解决阶乘、斐波那契数列和回文数问题

递归函数，就是在函数体内调用自己的函数。递归函数将反复调用其自身，每调用一次就进入新的一层，当最内层的函数执行完毕后，再一层一层地由里到外退出。因此，递归函数的优缺点也非常明显。

优点：思路和代码简单

缺点：占用内存多，效率低

编写递归函数，最重要的是要牢牢掌握好递归函数的两个条件，如果不能满足这两个条件，递归函数就会变成死循环！

条件：

1、递归函数必须有出口

2、必须不断地向出口靠近

下面用三个典型的问题来分析递归函数的写法：

一、阶乘

1、阶乘描述

自然数n的阶乘写作n!，n!=1×2×3×...×(n-1)×n，0!=1

2、递归条件

• 递归出口是0!=1
• n!=n*(n-1)!，n-1就是不断向出口靠近的条件

3、实现代码

# 定义递归函数
def fac(n):
    if n == 0:
        return 1
    else:
        return n * fac(n - 1)

# 求出给定数字的阶乘
a = 0
b = 1
c = 10
d = 18
print('%d的阶乘是：' % a, fac(a))
print('%d的阶乘是：' % b, fac(b))
print('%d的阶乘是：' % c, fac(c))
print('%d的阶乘是：' % d, fac(d))

输出结果：
0的阶乘是： 1
1的阶乘是： 1
10的阶乘是： 3628800
18的阶乘是： 6402373705728000           

二、斐波那契数列

1、斐波那契数列描述

数列形式：1、1、2、3、5、8、13、21、34、……

第一个数字是1，第二个数字也是1，以后每个数字都是前两个数字的和

2、递归条件

• 递归出口是F(1)=1，F(2)=1
• 向出口靠近的条件是F(n)=F(n - 1)+F(n - 2)

3、实现代码

# 定义递归函数
def fib(n):
    if n == 1:
        return 1
    elif n == 2:
        return 1
    else:
        return fib(n - 1) + fib(n - 2)

# 输入一个数字，输出这个数字长度的斐波那契数列
n = int(input('请输入斐波那契数列的长度：'))
print([fib(i) for i in range(1, n + 1)])

输出结果：
请输入斐波那契数列的长度：8
[1, 1, 2, 3, 5, 8, 13, 21]
请输入斐波那契数列的长度：15
[1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610]           

三、回文数

1、回文描述

“回文”Palindrome，是指正读和反读内容都一样的句子，应用在数学里，这样的数字叫回文数。例如：“level”、“noon”、“123454321”、“我为人人，人人为我”等等。

2、递归条件

• 单个字符一定是回文，因此递归出口是字符串长度小于2
• 先比较字符串前后两端的字符，再比较去掉前后字符后里面的字符串是否是回文，每一次都去掉前后两端字符，不断向出口靠近。最后，如果每层比较结果都为真，那么这个字符串就是回文；如果有一层比较结果是假，那么这个字符串就不是回文。
• 例如：level，是否为回文('level')，l==l，结果为True；是否为回文('eve')，e==e，结果为True；是否为回文('v')，字符串长度小于2，结果为True。返回：True & True & True，最后结果为True，level是回文。

3、实现代码

# 定义递归函数
def isPalindrome(string):
    if len(string) < 2:
        return True
    else:
        return (string[0] == string[len(string) - 1]) & isPalindrome(string[1:len(string) - 1])

# 设置需要判断的字符串列表
str_list = ['abcde', '我为人人，人人为我', 't', 'level', 'noon', '123454321', 'aberba']
# 遍历列表，判断是否为回文
for i in str_list:
    if isPalindrome(i):
        print(f'“{i}”是回文数')
    else:
        print(f'“{i}”不是回文数')

输出结果：
“abcde”不是回文数
“我为人人，人人为我”是回文数
“t”是回文数
“level”是回文数
“noon”是回文数
“123454321”是回文数
“aberba”不是回文数