python-函数的递归（可视化逻辑过程）_python递归函数 动画

python-函数的递归及可视化逻辑过程

本篇文章从什么是递归的角度出发，并且提供从简单题目、可视化逻辑过程帮助理解递归

递归是什么？

递归是一种在函数体内调用自身的编程技巧。通过递归，一个问题可以被分解成更小的子问题，直到达到某个终止条件，然后逐层返回结果，最终解决原始问题。

递归函数通常包含两个部分：递归调用和终止条件。递归调用是指函数在其自身内部调用自身。终止条件是指确定递归何时结束的条件，避免进入无限循环。

递归函数的实现方式通常遵循以下步骤：

1. 定义函数：首先定义一个函数，确定函数的输入参数和返回值。
2. 编写终止条件：在函数体内部，判断是否满足递归的终止条件。如果满足，返回特定的值或执行特定的操作。
3. 处理递归情况：如果未满足终止条件，执行递归调用，将问题分解为更小的子问题。通常需要调整函数的输入参数，使问题规模减小，接着再次调用函数本身。
4. 返回结果：在递归调用返回后，根据子问题的结果进行计算或操作，并返回最终结果。

下面是一个可视化的递归过程的例子，以计算阶乘（factorial）为例：

factorial(n):
    if n == 0:  // 终止条件
        return 1
    else:
        return n * factorial(n - 1)  // 递归调用
1
2
3
4
5

递归的调用栈示意图：

factorial(5)
  -> 5 * factorial(4)
       -> 4 * factorial(3)
            -> 3 * factorial(2)
                 -> 2 * factorial(1)
                      -> 1 * factorial(0)
                           -> return 1
                      -> return 1 * 1 = 1
                 -> return 2 * 1 = 2
            -> return 3 * 2 = 6
       -> return 4 * 6 = 24
  -> return 5 * 24 = 120
1
2
3
4
5
6
7
8
9
10
11
12

递归函数的调用过程是层层嵌套的，每个递归调用都会创建一个新的函数执行上下文（函数的局部变量等），直到达到终止条件后开始逐层返回结果。

以下是一个使用递归计算斐波那契数列的例子：

def fibonacci(n):
    if n <= 1:  # 终止条件
        return n
    else:
        return fibonacci(n-1) + fibonacci(n-2)  # 递归调用

# 调用示例
print(fibonacci(5))  # 输出: 5
1
2
3
4
5
6
7
8

题目：

1. 编写一个递归函数，计算给定数字的阶乘。
2. 编写一个递归函数，计算给定数字的斐波那契数列的第n项。
3. 编写一个递归函数，实现整数列表的反转。
4. 编写一个递归函数，检查给定字符串是否是回文（正读和反读都一样）。
5. 编写一个递归函数，计算给定数字的幂。

题目解答及其可视化逻辑过程

1. 编写一个递归函数，计算给定数字的阶乘。

def factorial(n):
    if n == 0:  # 终止条件
        return 1
    else:
        return n * factorial(n - 1)  # 递归调用

# 调用示例
print(factorial(5))  # 输出: 120
1
2
3
4
5
6
7
8

递归调用栈示意图：

factorial(5)
  -> 5 * factorial(4)
       -> 4 * factorial(3)
            -> 3 * factorial(2)
                 -> 2 * factorial(1)
                      -> 1 * factorial(0)
                           -> return 1
                      -> return 1 * 1 = 1
                 -> return 2 * 1 = 2
            -> return 3 * 2 = 6
       -> return 4 * 6 = 24
  -> return 5 * 24 = 120
1
2
3
4
5
6
7
8
9
10
11
12

2. 编写一个递归函数，计算斐波那契数列的第n项。

def fibonacci(n):
    if n <= 1:  # 终止条件
        return n
    else:
        return fibonacci(n-1) + fibonacci(n-2)  # 递归调用

# 调用示例
print(fibonacci(6))  # 输出: 8
1
2
3
4
5
6
7
8

递归调用栈示意图：

fibonacci(6)
  -> fibonacci(5) + fibonacci(4)
       -> fibonacci(4) + fibonacci(3) + fibonacci(3) + fibonacci(2)
            -> fibonacci(3) + fibonacci(2) + fibonacci(2) + fibonacci(1) + fibonacci(2) + fibonacci(1) + fibonacci(1) + fibonacci(0)
                 -> fibonacci(2) + fibonacci(1) + fibonacci(1) + fibonacci(0) + fibonacci(1) + fibonacci(0) + fibonacci(1) + fibonacci(0) + fibonacci(1)
                      -> fibonacci(1) + fibonacci(0) + fibonacci(1) + fibonacci(0) + fibonacci(1) + fibonacci(0) + fibonacci(1) + fibonacci(0) + fibonacci(1)
                           -> return 1
                      -> return 1 + 0 + 1 + 0 + 1 + 0 + 1 + 0 + 1 = 5
                 -> return 1 + 1 + 0 + 1 + 0 + 1 + 0 + 1 + 0 + 1 = 8
            -> return 2 + 1 + 1 + 0 + 1 + 0 + 1 + 0 + 1 + 0 + 1 + 1 + 0 + 1 + 0 + 1 + 0 = 13
       -> return 3 + 2 + 1 + 1 + 0 + 1 + 0 + 1 + 0 + 1 + 0 + 1 + 1 + 0 + 1 + 0 + 1 + 0 = 21
  -> return 5 + 8 = 13
1
2
3
4
5
6
7
8
9
10
11
12

3. 编写一个递归函数，实现整数列表的反转。

def reverse_list(lst):
    if len(lst) == 0:  # 终止条件
       

 return []
    else:
        return [lst[-1]] + reverse_list(lst[:-1])  # 递归调用

# 调用示例
print(reverse_list([1, 2, 3, 4, 5]))  # 输出: [5, 4, 3, 2, 1]
1
2
3
4
5
6
7
8
9
10

递归调用栈示意图：

reverse_list([1, 2, 3, 4, 5])
  -> [5] + reverse_list([1, 2, 3, 4])
       -> [4] + reverse_list([1, 2, 3])
            -> [3] + reverse_list([1, 2])
                 -> [2] + reverse_list([1])
                      -> [1] + reverse_list([])
                           -> return []
                      -> return [1] + [] = [1]
                 -> return [2] + [1] = [2, 1]
            -> return [3] + [2, 1] = [3, 2, 1]
       -> return [4] + [3, 2, 1] = [4, 3, 2, 1]
  -> return [5] + [4, 3, 2, 1] = [5, 4, 3, 2, 1]
1
2
3
4
5
6
7
8
9
10
11
12

4. 编写一个递归函数，检查给定字符串是否是回文（正读和反读都一样）。

def is_palindrome(s):
    if len(s) <= 1:  # 终止条件
        return True
    else:
        if s[0] == s[-1]:
            return is_palindrome(s[1:-1])  # 递归调用
        else:
            return False

# 调用示例
print(is_palindrome("radar"))  # 输出: True
print(is_palindrome("hello"))  # 输出: False
1
2
3
4
5
6
7
8
9
10
11
12

递归调用栈示意图（以输入"radar"为例）：

is_palindrome("radar")
  -> is_palindrome("ada")
       -> is_palindrome("d")
            -> return True
       -> return True
  -> return True
1
2
3
4
5
6

5. 编写一个递归函数，计算给定数字的幂。

def power(base, exponent):
    if exponent == 0:  # 终止条件
        return 1
    else:
        return base * power(base, exponent - 1)  # 递归调用

# 调用示例
print(power(2, 3))  # 输出: 8
1
2
3
4
5
6
7
8

递归调用栈示意图：

power(2, 3)
  -> 2 * power(2, 2)
       -> 2 * power(2, 1)
            -> 2 * power(2, 0)
                 -> return 1
            -> return 2 * 1 = 2
       -> return 2 * 2 = 4
  -> return 2 * 4 = 8

1
2
3
4
5
6
7
8
9