递归函数及其应用场景

递归函数是在函数内部调用函数本身的一种编程技术。它是在数学和计算机科学中广泛使用的一种技术。递归函数在某些情况下很好用，非常简单和优雅。在递归过程中，问题被切分成子问题，直到达到基本情况（基本条件）。这个过程使得代码更加清晰，同时也会使得代码更加简短和可读。在本文中，我们将讨论递归函数及其应用场景。

递归函数的应用场景：

1. 阶乘计算

$n! = n \times (n-1) \times (n-2) \times ... \times 1$

递归方式：

$factorial(n) = n \times factorial(n-1)$

注意：必须有一个终止条件，即 $factorial(1) = 1$

如何计算 $5!$：

$factorial(5) = 5 \times factorial(4)$

$factorial(4) = 4 \times factorial(3)$

$factorial(3) = 3 \times factorial(2)$

$factorial(2) = 2 \times factorial(1)$

$factorial(1) = 1$

$factorial(2) = 2 \times 1 = 2$

$factorial(3) = 3 \times 2 = 6$

$factorial(4) = 4 \times 6 = 24$

$factorial(5) = 5 \times 24 = 120$

2. 斐波那契数列

斐波那契数列的前两个数字是 0 和 1，后面的数字等于前面两个数字之和。例如：0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

递归式：

$Fib(0) = 0$

$Fib(1) = 1$

$Fib(n) = Fib(n-1) + Fib(n-2)$

如何计算斐波那契数列中的第 7 位数：

$Fib(7) = Fib(6) + Fib(5)$

$Fib(6) = Fib(5) + Fib(4)$

$Fib(5) = Fib(4) + Fib(3)$

$Fib(4) = Fib(3) + Fib(2)$

$Fib(3) = Fib(2) + Fib(1)$

$Fib(2) = Fib(1) + Fib(0)$

$Fib(1) = 1$

$Fib(0) = 0$

$Fib(2) = 1 + 0 = 1$

$Fib(3) = 1 + 1 = 2$

$Fib(4) = 2 + 1 = 3$

$Fib(5) = 3 + 2 = 5$

$Fib(6) = 5 + 3 = 8$

$Fib(7) = 8 + 5 = 13$

3. 二叉树遍历

在二叉树遍历中，我们可以使用递归函数，在左节点中遍历左子树，在右节点中遍历右子树。以下是二叉树的递归遍历函数：

a. 先序遍历 (Preorder Traversal)

先输出根节点，然后是左子树，再是右子树。

void Preorder(Node* node) {  

    if (node == NULL) return;  

    cout << node->value << " ";  

    Preorder(node->left);  

    Preorder(node->right);  

}  

b. 中序遍历 (Inorder Traversal)

先输出左子树，然后是根节点，再是右子树。

void Inorder(Node* node) {  

    if (node == NULL) return;  

    Inorder(node->left);  

    cout << node->value << " ";  

    Inorder(node->right);  

}  

c. 后序遍历 (Postorder Traversal)

先输出左子树，然后是右子树，再是根节点。

void Postorder(Node* node) {  

    if (node == NULL) return;  

    Postorder(node->left);  

    Postorder(node->right);  

    cout << node->value << " ";  

}  

总结

递归函数在算法中的使用非常广泛，常常用于树型问题、排列组合问题、跳台阶问题等等。在实现递归函数时，不要忘记终止条件，避免出现无限递归的情况；同时也要注意递归深度的问题，对于过深的递归，可以考虑改用迭代的方式实现。