递归函数的写法及其应用场景

递归函数是一种特殊的函数，它会在函数执行过程中反复调用自身。其主要应用场景包括数学运算、数据结构和算法等领域，如阶乘、斐波那契数列、二叉树遍历等。

下面以阶乘函数为例，介绍递归函数的写法和应用场景。

阶乘函数的写法

递归函数的写法通常有两个要素：

1. 递归终止条件：该条件表示递归停止的条件，不再执行递归操作。

2. 递归关系：表示递归函数如何自己调用自己并向终止条件逼近。

下面是阶乘的递归函数的伪代码：

int factorial(int n){
    //递归终止条件
    if(n == 0 || n == 1){
        return 1;
    }
    //递归关系
    return n * factorial(n-1);
}

应用场景

递归函数在算法领域有着广泛的应用，比如快速排序、归并排序、二叉树遍历等。下面分别介绍其中两个应用场景。

1. 斐波那契数列

斐波那契数列是指：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ……（数列中的第n个数等于前两个数之和）。

斐波那契数列的递归函数如下：

int fibonacci(int n){
    //递归终止条件
    if(n == 1 || n == 2){
        return 1;
    }
    //递归关系
    return fibonacci(n-1) + fibonacci(n-2);
}

斐波那契数列还有一种迭代实现的方式，但递归函数的可读性更强。

2. 二叉树遍历

二叉树是一种树形结构，其中每个节点最多有两个子节点，可以用递归函数实现遍历操作。

二叉树的遍历包括前序遍历、中序遍历和后序遍历：

- 前序遍历：根节点 -> 左子树 -> 右子树

- 中序遍历：左子树 -> 根节点 -> 右子树

- 后序遍历：左子树 -> 右子树 -> 根节点

二叉树的递归遍历函数示例：

//前序遍历
void preorderTraversal(TreeNode* root) {
    if(root == NULL) return;
    //根节点
    cout << root -> val << endl; 
    //左子树
    preorderTraversal(root -> left); 
    //右子树
    preorderTraversal(root -> right); 
}

//中序遍历
void inorderTraversal(TreeNode* root) {
    if(root == NULL) return;
    //左子树
    inorderTraversal(root -> left); 
    //根节点
    cout << root -> val << endl; 
    //右子树
    inorderTraversal(root -> right); 
}

//后序遍历
void postorderTraversal(TreeNode* root) {
    if(root == NULL) return;
    //左子树
    postorderTraversal(root -> left); 
    //右子树
    postorderTraversal(root -> right); 
    //根节点
    cout << root -> val << endl; 
}

总结

递归函数是一种重要的编程工具，它可以使问题更清晰，代码更简洁。递归函数有时会消耗更多的内存，但这是值得权衡的，因为递归函数可以让我们较清晰地描述算法和数据结构。