递归算法应用
递归程序设计是一个重要的程序设计思想。可以应用递归设计来解决字符串，链表，树中一些常见的问题。尤其是树中，很多问题都可以使用递归的方法来解决。在利用递归解决问题的时候，有2个关键的地方：
首先就是要找到问题的最简子问题，也就是问题中最简单的情况，比如对于一个链表，最简单情况就是链表为空或者只有一个结点；对于一个字符串，最简单情况就是字符串为NULL或者只有一个’\
然后是要通过分析和转换，将原问题转化为子问题。子问题和原问题是同类问题，但子问题的规模应该比原问题要小。比如求n!那么它的子问题就是(n-1)!，只需要把(n-1)!乘以n就是n的阶乘了。又比如要求斐波那契数列的第n个值，只需要求出(n-1)的值和(n-2)的值，那么就可以求出n的值了。在先序遍历树t的时候，当把根节点遍历完后，因为t->left和t->right是它的子树，也就是子问题，所以然后用递归遍历t->left和t->right就可以了。
14.6.1 字符串长度计算
问题：不允许使用任何全局或局部变量编写 int strlen(char *s)，计算字符串的长度。
分析：
递归出口即最简子问题：
S==NULL 长度为0
*s==’\
原问题与子问题的转化：
s是一个字符串，s+1也是一个字符串，而且是s的子串，所以只需要求出s+1字符串的长度，再加1就是s的长度，即：
1+strlen(s+1)
因此可以得出下面的算法：
size_t strlen(const char *s)
{
if(s==NULL || *s==’\
{
return 0;
}
return 1+strlen(s+1);
}
或者用三元运算符，进一步简化为：
size_t strlen( const char* s )
{
return (s==NULL||*s==’\
}
14.6.2 反向输出字符串
问题：请反向的输出一个字符串：比如”hello, world!”，打印出来是：”!dlrow, olleh”。
分析：
递归出口：
当字符串为NULL或者为’\
递归子问题：
要反向输出字符串，只需要将s+1这个子串输出后，再输出*s（即字符串s的第一个字符），即完成反向打印。
void inverse_print(char *s)
{
if( *s = = '\0'||s==NULL )
return;
inverse_print( s+1 );//先递归反向打印s的子串s+1
printf( "%c", *s );
}
14.6.3 递归实现链表转置。
将一个单向链表进行转置，使其头变尾，尾变头，各个结点指向它的前个结点。如下图所示：
分析：
递归的出口：当链表为空或者只有一个结点，不用处理，直接返回
递归子问题：只要将链表head的子链表：head->next逆置了，然后将head->next的尾结点指向head，那么整个链表head就得到了逆置。
typedef struct _node
{
int value;
struct _node *next;
}node,*list
list resverse_list(list l)
{
if(!l || !l->next)
return l;
list n = resverse_list (l->next);//先逆置l->next子链表,逆置后l->next即为l->next的尾结点
l->next->next = l;//把子链表的尾结点l->next指向l，l就变为了尾结点
l->next=null;//将尾结点的next指针设置为NULL
return n;
}
14.6.4 字符串逆置
用递归的方法将一个字符串逆置，比如”hello
world”à”dlrow
olleh”。
分析：
最简子问题（递归出口）：str==NULL或者len==1或者len==0,这个时候，不需要逆置
子问题转化：只要将str+1，长度为len-2的子串用同样的方法进行逆置之后，再将字符串最左边与最右边的字符交换了，即可完成字符串的逆置。
比如”hello
world”，先逆置除了最左边和最右边字符的子串：”ello
worl”，然后再交换’h’和’d’:
void reverse_str(char *str，size_t
len)
{
if(str==NULL || len==1||len==0)
return;
reverse_str(str+1,len-2);//先逆置子串
char tmp=*str;//再交换主串最左边与最右边的字符
*str=*(str+len-1)
*(st+len-1)=tmp;
}
14.6.5 台阶问题
有一个50阶的楼梯，每次可以上一阶或者两阶，总共的方法有多少种。
分析：
最简子问题（递归出口）：当只有1个台阶的时候，走法为1种；当有2个台阶的时候，走法有2个（一次上1阶，或者一次上2阶）。
子问题转化：在到达第n个台阶的时候，必然会经过第n-1或者n-2个台阶。那么，当一个人到达n-1个台阶的时候，他向上走一步就可以到达第n个台阶，所以，前往n个台阶的走法包含了n-1个台阶的走法数，记为f(n-1)；当一个人到达第n-2个台阶的时候，他向前一次走2个台阶就可以到达第n个台阶或者向前一次走1个台阶共走2步即可到达第n个台阶，由于一次走1个台阶会走到n-1个台阶，这种走法已经被包含在了n-1个台阶的走法中，所以只需要考虑从第n-2个台阶一次走2个台阶达到第n个台阶，假如到达n-2个台阶的走法为f(n-2)，那么可以得出，到达第n个台阶的走法实际上是达到n-1个台阶和n-2个台阶的总和，因为当这个人走到了n-1个台阶或者n-2个台阶的时候，它再向前的走法都是唯一的了。于是得出下面的公式：
f(1)=1
f(2)=2
f(3)=3
f(n)=f(n-1)+f(n-2)
long step_method_num(size_t n)
{
if(n==1)
return 1;
if(n==2)
return 2;
return step_method_num(n-1)+step_method_num(n-2);
}
14.6.6 求一棵树中2个结点的最近公共结点。
如下图所示：结点1和6的最近公共结点是3。
2个结点的最近公共结点的本质是这2个结点，一个在某个结点的左子树，一个在某个结点的右子树，那么该结点必然是这2个结点的最近公共结点。因此，只要在遍历该树的时候，对于遍历中的每一个结点，判断这2个结点是不是分别在这个结点的左右子树上，如果是，则该结点即为最近公共结点。如果这2个结点都在该结点的左子树，那么就递归判断左子树；在右子树，就递归判断右子树。
判断一个值是不是在树中：
bool search_tree(btree *t, int value)
{
if(t==NULL)
return false;
if(t->value==value)
return true;
return (search_tree(t->left,value) || search_tree(t->right,value));
}
查找2个结点v1,v2的公共结点，放入res中。成功返回1，失败返回0。
int find_lowest_common_node(btree *t, int v1,int v2,int *res)
{
if(t==NULL || res==NULL)
return 0;
bool v1_beleft=false;
bool v1_beright= false;
bool v2_beleft= false;
bool v2_beright= false;
v1_beleft=search_tree(t->left,v1);
if(!v1_beleft)
v1_beright=search_tree(t->right,v1);
v2_beleft=search_tree(t->left,v2);
if(!v2_beleft)
v2_beright=search_tree(t->right,v2)
//v1,v2分别在该结点的左右子树
if(v1_beleft&&v2_beright ||
v2_beleft&&v1_beright)
{
*res=t->value;
return 1;
}
//v1,v2在结点的左子树，递归查找左子树
if(v1_beleft && v2_beleft)
return find_loweset_common_node(t->left,v1,v2,res);
//v1,v2在结点的右子树，递归查找右子树
return find_loweset_common_node(t->right,v1,v2,res);
}
或者：
TreeNode* lowestCommanAncestor(TreeNode* root, TreeNode* p, TreeNode* q)
{
//这个完成了“找没找到”的功能（递归边界）
if(!root || root == p || root == q) return root;
//递归调用
TreeNode* left = lowestCommonAncestor(root->left, p, q);
TreeNode* right = lowestCommonAncestor(root->right, p, q);
//递归表达式（在左右递归调用完后）
//第一种情况
if(!left && !right) return NULL;
//第二种情况
else if(left && !right) return left;
//第三种情况
else if(!left && right) return right;
//第四种情况
return root;
}
14.6.7 递归与非递归快速排序
#include <stdio.h>
typedef struct _data {
int low;
int high;
}DATA;
#define MAX 100
void quick_sort2(int a[], int low, int high) {
DATA stack[MAX]={0};
int top = 0;
stack[0].low = low;
stack[0].high = high;
while(top>=0){
int l = stack[top].low;
int i = stack[top].low;
int j = stack[top].high;
int h = stack[top].high;
top--;
if(i>=j) {
continue;
}
int tmp = a[i];
while(i<j) {
while(a[j]>=tmp&&i<j) {
j--;
}
if(i<j) {
a[i] = a[j];
i++;
}
while(a[i]<=tmp&&i<j) {
i++;
}
if(i<j) {
a[j]=a[i];
j--;
}
}
a[i]=tmp;
DATA data;
data.low = l;
data.high = i-1;
if(top<MAX){
top++;
stack[top] = data;
}
data.low = i+1;
data.high = h;
if(top<MAX) {
top++;
stack[top] = data;
}
}
}
void quick_sort1(int a[], int low, int high) {
if(low>=high) {
return;
}
int i = low;
int j = high;
int tmp = a[i];
while(i<j) {
while(a[j]>=tmp && i<j) {
j--;
}
if(i<j) {
a[i] = a[j];
i++;
}
while(a[i]<=tmp&&i<j) {
i++;
}
if(i<j) {
a[j]=a[i];
j--;
}
}
a[i] = tmp;
quick_sort1(a,low, i-1);
quick_sort1(a,i+1, high);
}
void qsort(int a[], int len) {
quick_sort2(a, 0, len-1);
}
int _tmain(int argc, _TCHAR* argv[])
{
int a[]={5, 7, 6, 11, 1, 2,8};
qsort(a, sizeof(a)/sizeof(a[0]));
for(int i=0;i<sizeof(a)/sizeof(a[0]);i++) {
printf("%d,", a[i]);
}
printf("\n");
return 0;
}
