递归和迭代详解
递归和迭代详解
递归和迭代
递归(Recursion)和迭代(Iteration)是编程当中出现频率非常高的两个概念。对于迭代，理解起来自然是没有难度的，就是从头去遍历某个数据结构，到终点就退出。所以迭代非常适用于处理一些单向且线性的数据结构。下图是迭代的流程示意图。
但递归确实一个令许多人头疼的问题，因为在实现的迭代的过程中，经常需要函数自己调用自己，就跟套娃一样。而递归的过程其实分为两个部分，第一个部分是前向的去遍历数据结构，这点和迭代完全一样。而另一部分则是从终点方向迭代回起点。两个部分以调用函数本身的指令为分界线。下图是递归的示意图。
递归非常适用于处理一些反向任务，同时在处理一些套娃任务也有十分高效。为加深理解，下面举两个例子。
例子一
设当前有一个N结点的链表，每一个节点有一个height变量。现希望写一个程序，让最末端的节点height为0，倒数第二的节点height为1，依次类推，位于头部的节点height为N。注：N是一个未知数。
分析：由于我们不知道N是多少，所以如果使用迭代的方法，得先遍历一次链表，然后得到N。在遍历一遍链表，再依次给各个节点的height赋值。也就是说使用迭代的方法需要遍历两次链表。
而如果使用递归的方法，我们可以让其递归到最末端，然后从尾巴到首部，依次给各个节点的height赋值。只需要遍历一遍。
以下是用递归实现的程序：
#include <iostream>
#define N 9 //请假装不知道N
using namespace std;
struct Node
{
int height;
Node* next;
};
Node* GetLinklist(void) //构建一个N节点的链表
{
Node* root = nullptr;
Node* mid = nullptr;
for(int i = 0; i < N; i++)
{
Node* temp = new Node;
if(i == 0){
root = temp;
mid = temp;
}
else{
mid->next = temp;
mid = temp;
}
}
mid->next = nullptr;
return root;
}
void AssignData(Node* node)
{
static int cnt = 0; //cnt会被放在静态存储区，所以无论递归都少次，都只会被定义一次
if(node == nullptr) return; //递归结束的判断条件
AssignData(node->next); //自己调用自己，也是前向和后向的分界线
//以下代码是从尾部到首部才会执行的
node->height = cnt;
cnt++;
}
int main()
{
Node* root = GetLinklist();
AssignData(root);
return 0;
}
例子二
求一个二叉树的高度。二叉树的示意图如下：
分析：想要得到一棵树的高度，就得先得到其左子树和右子树的高度，再在两种中取得最大值。而为了得到左子树的高度，又得得到左左子树和左右子树的高度。。。如此套娃，直到最后一个节点。
于是，面对这样的套娃问题，不妨把一棵树多层次的树抽象为一个最简单的树，然后再使用递归去分别求得左右子树的高度。如图：
struct Node
{
int data;
Node* right;
Node* left;
};
int get_height(Node* node)
{
if(node == nullptr) return 0;
return max(get_height(node->left), get_height(node->right)) + 1;
}
int main()
{
Node* root = nullptr; //假设root是一个多层树的根
get_height(root);
return 0;
}
即便如此，相比递归也不是很好理解。那不凡手动标出这个树的前向遍历顺序和反向遍历顺序。如图，黑色的是前向遍历的顺序，红色是反向遍历的顺序。而根据要求不同，我们即可以在函数调用自己之前写一些代码，让这些代码在前向遍历的时候执行。也可以在函数调用之后些一些代码，让代码在反向遍历的时候再执行。