python 递归函数应用题

在Python中，递归函数是一种函数调用自身的技术，常用于解决那些可以分解为相似或相同子问题的问题。递归的应用题很多，例如：

1. **斐波那契数列**：经典的递归问题，每一项都是前两项之和，如`fib(0)` = 0, `fib(1)` = 1, `fib(n)` = `fib(n-1) + fib(n-2)`。递归版代码通常是`def fib(n): return n if n <= 1 else fib(n-1) + fib(n-2)`。

2. **阶乘计算**：求一个整数n的阶乘，即所有小于及等于n的正整数相乘，递归版本可以写成`def factorial(n): return 1 if n == 0 else n * factorial(n-1)`。

3. **汉诺塔**：这是一个涉及盘子移动的经典问题，递归策略是将大盘子从A柱移动到B柱，然后把小盘子移到C柱，最后再把大盘子从B柱移到C柱。

4. **二叉树遍历**（深度优先搜索，如前序、中序和后序遍历），通过递归处理每个节点及其子节点。

5. **分治算法**：如快速排序和合并排序等，它们通常包含一个递归的“分解”阶段和一个“合并”阶段。

相关问题

递归python习题

递归在Python中是一种重要的编程技巧，可以利用递归解决各种问题。下面是两个递归的Python习题：

1. 计算一个整数的阶乘（Factorial）：

def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n-1)

2. 给定一个整数列表，编写一个递归函数来计算列表中所有元素的和：

def sum_list(lst):
    if len(lst) == 0:
        return 0
    else:
        return lst[0] + sum_list(lst[1:])

以上是两个简单的递归习题，分别用于计算阶乘和列表元素求和。通过这些例子，你可以更好地理解递归的应用。

编程用递归函数实现1+2+3+4+……+n,并显示所求的和，其中n从键盘输入。（期末考试题，20分）

好的，这是一个经典的递归问题。以下是一个实现：

def sum_n(n):
    if n == 0:
        return 0
    else:
        return n + sum_n(n-1)

n = int(input("请输入n的值："))
result = sum_n(n)
print("1到n的和是：", result)

首先，定义了一个名为 `sum_n` 的递归函数，接收一个整数参数 `n`，表示需要求和的范围。如果 `n` 等于 0，则返回 0；否则，递归调用 `sum_n` 函数，传入参数 `n-1`，并将其返回值加上 `n`。

然后，从键盘读取 `n` 的值，并调用 `sum_n` 函数，将其结果存储在变量 `result` 中。最后，打印出 `result` 的值作为答案。

注意：这个递归函数的效率并不高，因为它在每一次递归调用时都会创建新的函数帧，占用大量的内存。在实际应用中，最好使用循环方式实现更高效的计算。