递归

　　在此之前分享一句话：递归是神，迭代是人。这里的神是针对数据结构这门课程，在实际应用中因为诸多的物理限制，导致递归可能因为栈溢出等，使用受限，其实如果是单纯数据结构这门课程，递归能为你节省相当多的麻烦，故递归是“神”！

　　有太多太多的同学匆匆就开始学习二叉树、链表等数据结构，对指针跟递归等基本概念都没有彻底明白，导致学习数据结构的时候只能知晓个大概，动手写的时候只能套用别人的，自己写憋半天，其实二叉树并不难，难是同学们的基础没有打牢实，就匆匆学习，从而产生畏惧心理学不全面，草草了事。

　　你已经见过许多基于循环的算法，它们一遍又一遍地执行某些任务。现在来讲另一类不使用循环却可以重复执行代码的方法，这种方法使用的是重复的函数调用，我们把它称为递归。递归是一种在表达操作时会用到自身的技术，也就是说，递归意味着编写的函数会调用自身。它跟循环类似，但功能更强大。它可以使某些几乎不可能用循环来完成的程序变成小事一桩！递归尤其适合于应用在诸如链表、二叉树（马上就讲到了）这样的数据结构中。接下来的两章内容，我们一起通过一些具体的例子，来探讨递归的基本思想。

如何看待递归

　　一个思考递归的有效方法是：把递归看做一个执行过程，这个执行过程的其中一条指令是“重复这个执行过程”。这听起来跟循环非常类似，因为都是在重复相同的代码。递归和循环确实在某些方面是类似的，但是，递归可以更容易地表达这样一种想法：执行过程的结果是完成执行过程所必需的。当然，这个“执行过程”必须存在某个时刻可以不用再递归调用就能够完成。举个简单的例子，砌筑一面10尺高墙。如果我想建造一面十英尺高的墙，我会先建造一个九英尺高的墙，然后添加一层额外的墙砖。从概念上讲，这就好比说：“建墙”函数接受了一个高度值，如果这个高度值大于1，“建墙”函数首先要调用自身来建造一个稍低的墙，然后添加一层额外的墙砖。

　　这个“建墙”函数的基本结构看起来应该如下面的代码所示。（这段代码有几个明显的缺陷，我们很快会讨论到。）这里面最重要的思想是：建造一个特定高度的墙可以用建造一个更低的墙来表达。

void buildWall (int height)
{
　　buildWall( height - 1 );
　　addBrickLayer();
}

　　但这段代码有一个小问题，不是吗？什么时候会停止调用buildWall呢？很遗憾，答案是，永远不。解决办法很简单：我们需要在墙高为0时停止递归调用。墙的高度为0时，我们应该仅仅添加一层墙砖即可，不用建造任何更低的墙体。
　　

void buildWall (int height)
{
　　if ( height > 0 )
　　{
　　buildWall( height - 1 );
　　}
　　addBrickLayer();
}

　　函数不调用自身的情况称为函数的基线条件。在刚才的例子中，“建墙”函数知道如果已经到达地面，就只要添加一层墙砖就可以了（建墙的基线条件）。否则，我们仍然需要建立一堵更低的墙，然后在上面添加一层砖。如果你对这段代码还是疑惑不解（第一次见到递归时，人们往往一头雾水），想想建造一堵墙的物理过程。刚开始，你希望建造一堵特定高度的墙，接着就会说：“我需要一堵矮一层的墙，好让我把砖块放上去。”最终，你就会说：“我不需要一堵更矮的墙了，我可以直接在地面上建造。”这就是基线条件。
　　

　　注意，这个算法先将一个大问题简化成更小的问题（建造一堵更矮的墙），然后去解决这个更小的问题。在某些情况下，更小的问题（如在地面上建造一层高的墙体）小到不再需要进一步简化，而是可以马上就解决。在现实生活中，这意味着可以建立一堵墙了；而在C++里，这确保了该函数将最终停止递归调用。这很像之前看到过的自顶向下的设计过程，我们把问题分解成更小的子问题，创建出这些子问题的函数，然后用它们来构建完整的程序。这种情况下，我们将问题分解成了不同的子问题，而不是一个正在解决的问题；而在递归中，我们将一个问题分解成了相同问题的更小版本。

　　一旦函数调用了自己，当调用返回时，它会去执行调用点之后的下一行语句。类似的，递归调用返回后，函数仍可以执行操作或调用其他函数。在“建墙”的例子中，建造小墙后，函数将继续执行，添加一层新的砖块。

　　下面是一个实际可运行的例子，用来展示实际的输出。怎样写出一个递归函数，来输出数字123 456 789 987 654 321呢？我们可以先编写一个函数，它接受一个数字，然后两次输出这个数字，一次在函数递归之前，一次在递归之后。
　　

#include <iostream>
using namespace std;
void printNum (int num)
{
　　// 函数的两次cout调用，将像“三明治”一样输出
　　// 形如 (num+1)...99...(num+1) 的数字序列
　　cout << num;
　　// 只要num小于9, 就递归输出
　　// 序列 (num+1) ... 99 ... (num+1)
　　if ( num < 9 )
　　{
　　printNum( num + 1 );
　　}
　　cout << num;
　　}
　　int main ()
　　{
　　printNum( 1 );
}

　　有些数据结构会借用到递归算法，因为这些数据结构的组成可以描述成含有相同数据结构的更小版本。既然递归算法通过将问题分解成原问题的更小版本来解决，数据结构也一样可以将原数据结构分解成相同数据结构的更小版本——链表就是一种这样的数据结构。

　　之前已经说过，链表是这样一种列表：你可以在链表前面增添更多的新节点。但从另一个角度去思考，也可以认为，链表由一个首节点构成，这个首节点指向了另一个更小版本的链表。

　　这一点很重要，因为它提供了一个非常有用的特性：可以编写这样一种处理链表的程序，它要么处理当前节点，要么去处理“列表的其余部分”。例如，要找到列表中的一个特定节点，可以使用此基本算法：
　　如果我们在列表的末尾，返回NULL。 否则，如果当前节点就是查找的目标，将其返回。否则，在列表的其余部分继续查找。

　　在代码中，应该是这样的：

struct node
{
　　int value;
　　node *next;
};
node* search (node* list, int value_to_find)
{
　　if ( list == NULL )
　　{
　　return NULL;
　　}
　　if ( list->value == value_to_find )
　　{
　　return list;
　　}
　　else
　　{
　　return search( list->next, value_to_find );
　　}
}

　　当考虑一个递归调用时，我们提到过，被调用函数中会做一些事情。函数在给定的输入下所承诺要做的事，称为函数的契约。函数契约总结了函数所要做的事情。search函数的契约是查找到列表中的一个给定的节点。search函数的实现就相当于在说，“如果当前节点是我们想要找的，那么返回它；否则，函数的契约还是在列表中查找某个节点，让我们用这个契约，来看看剩余的列表吧！”
　　在列表的剩余部分调用search函数，而不是整个列表，这一点很重要。
　　递归只有在满足以下两个条件时，才能够正确运行：

　　1.能够构造出一个通过解决同类型的较小问题来解决原问题的方案；
　　2.能够解决基线条件。

　　search函数的解决有两个可能的基线条件：要么到达列表的末尾，要么找到想要的节点。如果这两种情况都没有满足，那么使用search函数来解决相同问题的较小版本。关键在于：我们能够递归地利用相同问题的较小版本的解决结果，来解决更大的原问题，只有这样，递归才能起到效果。
　　请注意，使用递归的过程中，我们不断地求解子问题，然后用子问题的结果来做一些事。在搜索一个链表时，我们只是返回子问题的求解结果。递归用于两种方式：要么是仅靠递归调用就能够解决全部的问题，要么是获得子问题的求解结果，然后使用该结果做更多的计算。

　　在某些情况下，递归算法可以很容易地转化成用结构相同的循环来表示。例如，搜索列表的代码可以写成这样：

node *search (node *list, int value_to_find)
{
　　while ( 1 )
　　{
　　if ( list == NULL )
　　{
　　return NULL;
}
　　if ( list->value == value_to_find )
　　{
　　return list;
　　}
　　else
　　{
　　list = list->next;
　　}
}
}

　　这段代码进行的检查实际上跟使用递归的版本是一样的，你很容易看出两者的差异。两种算法的唯一区别是，这段代码使用了一个循环，而不是递归。它没有使用递归调用来缩短列表的大小，而是通过每次将它指向“列表的剩余部分”来实现的。这是一个递归的解决方案和迭代（基于循环）的解决方案有相似之处的例子。

　　当不需要对递归调用函数的返回值做任何处理时，通常很容易写出递归算法的循环版本，反之亦然，我们也能很容易写出循环算法的递归版本。这种情况就是尾递归（tail reursion）：递归调用是递归函数在函数尾部所做的最后一件事情。由于递归调用是最后一个操作，这无异于循环中的下一步。一旦下一个调用完成，之前的调用就不再需要了。列表搜索就是一个尾递归的例子。

二叉树

　　来看看结构化的数据到底是什么。刚开始时，你只会使用数组，数组仅仅是一个顺序列表，没有能力来提供其他任何数据结构。链表使用指针来逐步构建一个顺序列表，但它没有利用指针所具有的灵活性来构建更精巧的数据结构。

　　所谓的“更精巧的数据结构”指什么呢？首先，可以构建一个数据结构，它能够同时拥有不止一个“下一个节点”。为什么要这么做呢？如果你有两个“下一个节点”，其中一个代表比当前元素小的元素，另一个代表比当前元素大的元素，这种数据结构就称为二叉树。之所以如此命名，是因为在二叉树中，每个节点最多有两个分支。这里的“下一个节点”称为子节点，指向一个子节点的节点称为该子节点的父节点。

　　二叉树的一个重要特性是，一个节点的每个子节点本身就是一棵完整的二叉树。

　　这一特征，结合上“左子节点比当前节点小，右子节点比当前节点大”这一规则，使得寻找一棵树中的某个节点的算法设计起来很容易。首先，查看当前节点的值，如果它等于搜索目标，则搜索结束，大功告成；如果搜索目标小于当前节点的值，你往左边的树中找；否则，到右边的树去找。这个算法能够有效，主要因为左子树中的每个节点都小于当前节点，而右子树中的每个节点都大于当前节点。

　　最理想的二叉树是平衡树，即左子树与右子树的节点数量相同。对于一棵平衡树来说，每个子树是整棵树的一半大小，如果你正在查找树中的某个值，每到一个子节点，你的搜索就可以排除掉一半的元素。所以，如果有一棵1000个元素的平衡树，你可以立即砍掉500个元素。搜索就减少到在一棵500个元素的子树中进行。对一棵500个元素的树进行搜索，我们再次可以砍掉大约一半的元素，约250个。继续这样每到一个节点就排除掉一半的元素，不用多久就能找到想要找的元素。总共需要多少次拆分树的操作才能到达只有一个节点的树呢？

　　答案是log2n，其中n为整棵树的节点数量。这个值很小，即使对于非常大的树（对于一棵约有40亿个元素的树，log2n为32，这意味着，其搜索速度比对同等大小的链表进行同样的搜索要快近1亿倍，因为在链表中你必须要逐个地查看每个元素 ) 。然而，如果这棵树不平衡，可能就不能每次砍去树的一半元素。在最坏情况下，每个节点只有一个子节点，也就是说这棵树本质上是一个链表，只是比普通的链表多了一些额外的指针，那么其搜索过程就会退化到要遍历全部的n个元素。

　　如你所见，当一棵树大致平衡时（没有必要一定要完全平衡 ) ，搜索节点的速度要远远快于在链表中的搜索。这一切归根结底是因为我们可以根据自己的喜好来结构化内存，而不是止步于简单的列表1。

实现二叉树

让我们来看看简单实现一个二叉树所需的代码。首先，我们声明一个节点结构体：

struct node
{
　　int key_value;
　　node *p_left;
　　node *p_right;
};

　　我们的节点可以将key_value的值作为一个简单的整数值存储下来，并且包含两个子树，分别是p_left和p_right。

　　这几个是你会在二叉树上执行的常用函数：插入节点到树中，搜索树中的某个值，从树中删除某个节点，删除整棵树以释放内存。
　　

node* insert (node* p_tree, int key);
node *search (node* p_tree, int key);
void destroyTree (node* p_tree);
node *remove (node* p_tree, int key);

在树中插入新节点　

　　首先学习使用递归算法来实现树节点的插入。递归算法能用在树上，是因为每棵树都包含两棵更小的树，所以整个数据结构本身就是递归的。（假设每棵树都包含一个数组或是一个指向链表的指针，那么这种数据结构就不是递归的了。 )
　　函数接受一个key值和一棵已存在的树（可能为空 ) ，返回包含此插入值的新树。

node* insert (node *p_tree, int key)
{
　　// 基线条件：我们到达了一棵空树，需要将新节点插入到这里
　　if ( p_tree == NULL )
　　{
　　node* p_new_tree = new node;
　　p_new_tree->p_left = NULL;
　　p_new_tree->p_right = NULL;
　　p_new_tree->key_value = key;
　　return p_new_tree;
}
　　// 决定将新节点插入到左子树或右子树中
　　// 取决于新节点的值
　　if( key < p_tree->key_value )
　　{
　　// 根据p_tree -> left和新增的key值，构建一棵新树，
　　// 然后用一个指向新树的指针来替换现有的p_tree -> left
　　// 之所以需要替换现有的p_tree -> left，是为了防止
　　// 原有的p_tree -> left为NULL的情况（如果不为NULL，p_tree->p_left
　　// 实际上不会改变，但替换下也无妨）
　　p_tree->p_left = insert( p_tree->p_left, key );
}
　　else
　　{
　　// 插入到右子树的情况与插入到左子树是对称的
　　p_tree->p_right = insert( p_tree->p_right, key );
　　}
return p_tree;
}

　　此算法的基本逻辑是：如果当前拥有的是一棵空树，那就创建一棵新的树。若非空树，那么如果要插入的值大于当前节点，就将其插入左子树中，并用新创建的子树替换原来的左子树；否则就将新节点插入右子树中，并做同样的替换。

　　让我们在实例中看看这段代码——将一棵空树构建成有两个节点的树。如果将值10插入一棵空树（NULL ) 中，立即达到了基线条件，其结果是一棵非常简单的树：
　　这棵树的两个子树都指向了NULL。

　　如果再将值5插入到树中，将调用函数：

insert( <头为10的树>, 5 )

　　由于5比10小，我们将对左子树进行递归调用：

insert( NULL, 5 )
insert( <头为10的树>, 5 )

　　函数insert( NULL, 5 )将创建一棵新的树，并将它返回：

当函数insert( <头为10的树>, 5 )收到返回的树时，会将两棵树链接到一起。在这种情况下，头为10的树的左子树原本为NULL，被替换后就变成了一棵全新的树。

在树中搜索

　　现在，来看看如何实现在树中进行搜索，其基本逻辑与在树中插入新节点的算法几乎完全一样：首先，检查两个基线条件（是否发现目标节点，或是否到达了一个空树 ) ；如果基线条件不满足，就确定应该去哪个子树中搜索。

node *search (node *p_tree, int key)
{
　　// 如果到达了空树，很明显，值key不在这棵树中！
　　if ( p_tree == NULL )
　　{
　　return NULL;
　　}
　　// 如果找到了值key，搜索完成！
　　else if ( key == p_tree->key_value )
　　{
　　return p_tree;
　　}
　　// 否则，尝试在左子树或右子树中寻找
　　else if ( key < p_tree->key_value )
　　{
　　return search( p_tree->p_left, key );
　　}
　　else
　　{
　　return search( p_tree->p_right, key );
　　}
}

　　上面的search函数首先检查两个基线条件：是否到达树的分支末端或是否找到了值key。无论哪种情况，我们都知道应该返回什么：如果到达树的分支末端，就返回NULL；如果找到了key值，就返回这棵树本身。
　　

　　如果基线条件不满足，我们就在子树中找key值，从而减小了问题。在左子树还是在右子树中查找，取决于key的值。请注意，每次递归调用，树的大小正如本章开头所讲——约减少了一半。在本章开头，我们还看到，在一棵平衡二叉树中搜索所花费的时间正比于log2n，当数据量很大时，这远比通过链表或数组进行搜索要快得多。

删除树

　　destroy_tree函数也应该是递归的。该算法将先删除当前节点的两个子树，然后再删除当前节点。

void destroy_tree (node *p_tree)
{
　　if ( p_tree != NULL )
　　{
　　destroy_tree( p_tree->p_left );
　　destroy_tree( p_tree->p_right );
　　delete p_tree;
　　}
}

　　为了帮助理解整个递归调用过程，你可以在删除节点前输出节点的值：

void destroy_tree (node *p_tree)
{
　　if ( p_tree != NULL )
　　{
　　destroy_tree( p_tree->p_left );
　　destroy_tree( p_tree->p_right );
　　cout << "Deleting node: " << p_tree->key_value;
　　delete p_tree;
　　}
}

你会看到，那棵树是“自下而上”被删除的。节点5和节点8首先被删除，接着是节点6；然后删除树的另一边，删除节点11和节点18，接着是节点14；最后，当所有的子节点都被删除时，删除节点10。树中的值并不重要，重要的是节点的位置。我在下面的二叉树中放置的是节点删除的顺序，而不是每个节点的值：

等等！！