如果一个函数调用了自身，这样的函数就叫做“递归函数”（recursive function）。

递归

1. 递归的实现

递归是调用自身，如果不加限制，这个过程是不会结束的；函数永远调用自己下去，最终会导致程序栈空间耗尽。所以在递归函数中，一定会有某种“基准情况”，这个时候不会调用自身，而是直接返回结果。基准情况的处理保证了递归能够结束。

递归是不断地自我重复，这一点和循环有相似之处。事实上，递归和循环往往可以实现同样的功能。

比如之前求阶乘的函数，我们可以用递归的方式重新实现：

#include<iostream>

using namespace std;

// 递归方式求阶乘

int factorial(int n)

{

if (n == 1)

return 1;

else

return factorial(n - 1) * n;

}

int main()

{

cout << "5! = " << factorial(5) << endl;

cin.get();

}

这里我们的基准情况是n == 1，也就是当n不断减小，直到1时就结束递归直接返回。5的阶乘具体计算流程如下：

因为递归至少需要额外的栈空间开销，所以递归的效率往往会比循环低一些。不过在很多数学问题上，递归可以让代码非常简洁。

2. 经典递归——斐波那契数列

斐波那契数列（Fibonacci sequence），又称黄金分割数列，指的是这样一个数列：

1, 1, 2, 3, 5, 8, 13, 21, 34, …

它的规律是：当前数字，是之前两个数字之和。在数学上，斐波那契数列被以递推的方法定义：

F(0)=1，F(1)=1, F(n) = F(n - 1) + F(n - 2)（n ≥ 2，n ∈ N*）

这天然适合使用递归实现：

#include<iostream>

using namespace std;

int fib(int n)

{

if (n == 1 || n == 2)

return 1;

return fib(n - 2) + fib(n - 1);

}

int main()

{

cout << "fib(9) = " << fib(9) << endl;

cin.get();

}

应用案例

1. 二分查找

二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法，前提是数据对象必须先排好序。二分查找事实上采用的是一种“分治”策略，它充分利用了元素间的次序关系。

#include<iostream>

using namespace std;

// 可以递归调用的二分查找

int search(const int(&a)[10], int start, int end, int target)

{

// 基准情况：目标值超出范围，或者start > end，说明没有找到

if ( target < a[start] || target > a[end] || start > end)

return -1;

// 取二分的中间坐标

int mid = (start + end) / 2;

// 比较中间值和目标值的大小

if (a[mid] == target)

return mid; // 找到了

else if (a[mid] > target)

return search(a, start, mid - 1, target); // 比目标值大，在更小的部分找

else

return search(a, mid + 1, end, target); // 比目标值小，在更大的部分找

}

int main()

{

int arr[10] = { 1,2,3,4,5,6,9,12,25,38 };

int key = 25;

int size = sizeof(arr) / sizeof(arr[0]);

int result = search(arr, 0, size - 1, key);

result == -1

? cout << "在数组中没有找到" << key << "!" << endl

: cout << "在数组中找到" << key << "，索引下标为：" << result << endl;

cin.get();

}

2. 快速排序

之前介绍过两种对一组数据进行排序的算法：选择排序和冒泡排序，它们都需要使用两层for循环遍历数组，效率较低。一种巧妙的改进思路是：通过一次扫描，将待排记录分隔成独立的两部分，其中一部分的值全比另一部分的小；接下来分别对这两部分继续进行排序，最终全部排完。这种算法更加高效，被称为“快速排序”。

可以看出，快排也应用了分治思想，一般会用递归来实现。

#include<iostream>

using namespace std;

void quickSort(int(&)[10], int, int);

int partition(int(&)[10], int, int);

void printArr(const int(&)[10]);

void swap(int(&)[10], int, int);

int main()

{

int arr[10] = { 23, 45, 18, 6, 11, 19, 22, 18, 12, 9 };

printArr(arr);

int size = sizeof(arr) / sizeof(arr[0]);

quickSort(arr, 0, size - 1);

printArr(arr);

cin.get();

}

// 快速排序

void quickSort(int(&a)[10], int start, int end)

{

// 基准情况

if (start >= end)

return;

// 分区，返回分区点下标

int mid = partition(a, start, end);

// 递归调用，分别对两部分继续排序

quickSort(a, start, mid - 1);

quickSort(a, mid + 1, end);

}

// 按照pivot分区的函数

int partition(int(&a)[10], int start, int end)

{

// 选取一个分区的“支点”

int pivot = a[start];

int left = start, right = end;

while (left < right)

{

// 分别从左右两边遍历数组

while (a[left] <= pivot && left < right)

++left;

while (a[right] >= pivot && left < right)

--right;

// 左右互换

swap(a, left, right);

}

if (a[left] < pivot) {

swap(a, start, left);

return left;

}

else if (a[left] > pivot)

{

swap(a, start, left - 1);

return left - 1;

}

}

// 数组中两元素互换的函数

void swap(int(&a)[10], int i, int j)

{

int temp = a[i];

a[i] = a[j];

a[j] = temp;

}

// 打印输出一个数组

void printArr(const int(&a)[10])

{

for (int num : a)

cout << num << "\t";

cout << endl;

}

3. 遍历二叉树

跟数组不同，树是一种非线性的数据结构，是由n（n >=0）个节点组成的有限集合。如果n==0，树为空树。如果n>0，树有一个特定的节点，叫做根节点（root）。

对于树这种数据结构，使用最频繁的是二叉树。每个节点最多只有2个子节点的树，叫做二叉树。二叉树中，每个节点的子节点作为根的两个子树，一般叫做节点的左子树和右子树。

我们可以为树的节点定义一种结构体类型，而且为了方便以后在不同的文件中使用，还可以自定义一个头文件tree_node.h，将结构体TreeNode的定义放在里面：

#pragma once

#include<string>

using namespace std;

struct TreeNode

{

string name;

TreeNode* left;

TreeNode* right;

};

在别的文件中，如果想要使用TreeNode这个结构体，我们只要引入就可以：

#include "TreeNode.h"

对于树的遍历，主要有这样三种方式：

• 先序遍历：先访问根节点，再访问左子树，最后访问右子树；
• 中序遍历：先访问左子树，再访问根节点，最后访问右子树；
• 后序遍历：先访问左子树，再访问右子树，最后访问根节点。

这种遍历方式就隐含了“递归”的思路：左右子树本身又是一棵树，同样需要按照对应的规则来遍历。

我们可以先单独创建一个文件print_tree.cpp，实现二叉树的遍历方法：

#include<iostream>

#include "tree_node.h"

// 先序遍历打印二叉树

void printTreePreOrder(TreeNode* root)

{

// 基准情况，如果是空树，直接返回

if (root == nullptr) return;

//cout << (*root).name << "\t";

cout << root->name << "\t";

// 递归打印左右子树

printTreePreOrder(root->left);

printTreePreOrder(root->right);

}

// 中序遍历打印二叉树

void printTreeInOrder(TreeNode* root)

{

// 基准情况，如果是空树，直接返回

if (root == nullptr) return;

printTreeInOrder(root->left);

cout << root->name << "\t";

printTreeInOrder(root->right);

}

// 后序遍历打印二叉树

void printTreePostOrder(TreeNode* root)

{

// 基准情况，如果是空树，直接返回

if (root == nullptr) return;

printTreePostOrder(root->left);

printTreePostOrder(root->right);

cout << root->name << "\t";

}

然后将这些函数的声明也放到头文件tree_node.h中：

void printTreePreOrder(TreeNode* root);

void printTreeInOrder(TreeNode* root);

void printTreePostOrder(TreeNode* root);

接下来就可以在代码中实现具体的功能了：

#include<iostream>

#include "tree_node.h"

int main()

{

// 定义一棵二叉树

TreeNode nodeG = {"G", nullptr, nullptr};

TreeNode nodeF = { "F", nullptr, nullptr };

TreeNode nodeE = { "E", &nodeG, nullptr };

TreeNode nodeD = { "D", nullptr, nullptr };

TreeNode nodeC = { "C", nullptr, &nodeF};

TreeNode nodeB = { "B", &nodeD, &nodeE };

TreeNode nodeA = { "A", &nodeB, &nodeC };

TreeNode* tree = &nodeA;

printTreePreOrder(tree);

cout << endl << endl;

printTreeInOrder(tree);

cout << endl << endl;

printTreePostOrder(tree);

cin.get();

}