如果一个函数调用了自身，这样的函数就叫做“递归函数”（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();
}