函数的递归调用及应用

# 1. 什么是递归调用

## A. 定义及原理

在编程中，递归是指函数直接或间接调用自身的方式。递归调用是基于“递归关系”而展开的，它通过不断将问题拆解为更小的、相同类型的子问题来解决复杂的计算。递归的原理是将一个大问题分解成规模更小的子问题，通过解决这些子问题来达到解决整个大问题的目的。

## B. 递归调用的特点

1. 自相似性：递归调用的问题规模可以逐渐减小，直至达到终止条件。
2. 可读性：某些问题的递归解法比迭代更加直观和简洁。
3. 空间复杂度高：递归调用会消耗大量的栈空间，有可能导致栈溢出问题。
4. 效率低：相较于迭代，递归调用的效率通常较低，因为函数调用本身会产生额外的开销。

以上是递归的基本特点，接下来我们将详细介绍递归调用的基本实现方法。

# 2. 递归调用的基本实现方法

在实现递归调用时，需要注意函数内部调用自身，并设置递归终止条件。

### A.函数内部调用自身

递归调用的核心在于函数内部调用自身。通过函数内部调用自身，可以实现对同一个函数的反复调用，从而达到递归的效果。代码示例如下：

def recursive_function(n):
    if n <= 0:
        return
    else:
        print(n)
        recursive_function(n-1)

recursive_function(5)

public class RecursiveExample {
    public static void recursiveFunction(int n) {
        if (n <= 0) {
            return;
        } else {
            System.out.println(n);
            recursiveFunction(n - 1);
        }
    }

    public static void main(String[] args) {
        recursiveFunction(5);
    }
}

### B.递归终止条件的设置

递归调用必须设置递归终止条件，否则会导致无限递归，最终导致栈溢出错误。终止条件的设置是保证递归能够结束的关键。例如，在上述代码示例中，终止条件为`n <= 0`，当n小于等于0时，递归调用会终止。

def recursive_function(n):
    if n <= 0:
        return
    else:
        print(n)
        recursive_function(n-1)

recursive_function(5)

public class RecursiveExample {
    public static void recursiveFunction(int n) {
        if (n <= 0) {
            return;
        } else {
            System.out.println(n);
            recursiveFunction(n - 1);
        }
    }

    public static void main(String[] args) {
        recursiveFunction(5);
    }
}

通过以上代码示例，递归调用的基本实现方法已经介绍完毕。接下来，在第三章节中，我们将探讨递归调用的应用场景。

# 3. 递归调用的应用场景

A.经典示例：阶乘计算

递归调用在计算阶乘时非常常见。阶乘是指从1乘到给定数值的连续乘积。例如，5的阶乘（记作5!），即为1 * 2 * 3 * 4 * 5，结果为120。下面是一个用递归调用计算阶乘的示例代码：

**Python示例代码：**

def factorial(n):