建网站的工具/手游推广去哪里找客源

        今天我们来看看递归，那么我们为什么要讲递归呢？在后面的数据结构的学习中会用到递归的思想。递归是一种数学上分而自治的思想，将原问题分解为规模较小的问题进行处理。分解后的问题与原问题的类型完全相同，但规模较小；通过小规模问题的分解，能够轻易求得原问题的解。

        但问题的分解是有限的（递归不能无限进行），当边界条件不满足时，分解问题（递归继续进行）；当边界条件满足时，直接求解（递归结束）。下来我们来看看递归模型的一般表示法，如下

        递归在程序设计中的应用 -- 递归函数。1、函数体中存在自我调用的函数；2、递归函数必须有递归出口（边界条件）；3、函数的无线递归将导致程序崩溃。下来我们来看看递归思想的应用：

        1、求解：Sum( n ) = 1 + 2 + 3 + ... + n

        源码如下

#include <iostream>using namespace std;unsigned int sum(unsigned int n)
{if( n > 1 ){return n + sum(n-1);}else{return 1;}
}int main()
{cout << "sum(100) = " << sum(100) << endl;return 0;
}

        我们来看看运行结果

        2、斐波拉契数列：数列自身递归定义：1、1、2、3、5、8、13、21、...，它的定义是后一个的数字是前两个数字之和。

        源码如下

#include <iostream>using namespace std;unsigned int fac(unsigned int n)
{if( n > 2 ){return fac(n-1) + fac(n-2);}if( (n == 2) || (n == 1) ){return 1;}return 0;
}int main()
{for(int i=1; i<10; i++){cout << i << " : " << fac(i) << endl;}return 0;
}

        运行结果如下

        我们看到前 9 个的数字是完全一样的。

        3、用递归的方法编写函数求字符串长度，方法如下

        源码如下

#include <iostream>using namespace std;unsigned int _strlen_(const char* s)
{if( *s != '\0' ){return 1 + _strlen_(s+1);}else{return 0;}
}int main()
{cout << _strlen_("abc") << endl;return 0;
}

        运行结果如下

        那么我们上面的字符串长度的求解方法还有待优化，我们可以将上面的函数优化成下面的代码

#include <iostream>using namespace std;unsigned int _strlen_(const char* s)
{return s ? (*s ? (1 + _strlen_(s+1)) : 0) : 0;
}int main()
{cout << _strlen_("abcdef") << endl;return 0;
}

        我们来看看结果

        4、单向链表的转置，如下

        源码实现如下

#include <iostream>
#include <cstring>using namespace std;struct Node
{int value;Node* next;
};Node* create_list(int v, int len)
{Node* ret = NULL;Node* slider = NULL;for(int i=0; i<len; i++){Node* n = new Node();n->value = v++;n->next = NULL;if( slider == NULL ){slider = n;ret = n;}else{slider->next = n;slider = n;}}return ret;
}void destory_list(Node* list)
{while( list ){Node* del = list;list = list->next;delete del;}
}void print_list(Node* list)
{while( list ){cout << list->value << "->";list = list->next;}cout << "NULL" << endl;
}Node* reverse(Node* list)
{if( (list == NULL) || (list->next == NULL) ){return list;}else{Node* guard = list->next;Node* ret = reverse(list->next);guard->next = list;list->next = NULL;return ret;}
}int main()
{Node* list = create_list(1, 5);print_list(list);list = reverse(list);print_list(list);destory_list(list);return 0;
}

        运行结果如下

        我们看到第一次单向链表是 1->2->3->4->5->NULL；经过转置后的结果是 5->4->3->2->1->NULL。

        5、单向排序链表的合并，如下

        源码实现如下

#include <iostream>
#include <cstring>using namespace std;struct Node
{int value;Node* next;
};Node* create_list(int v, int len)
{Node* ret = NULL;Node* slider = NULL;for(int i=0; i<len; i++){Node* n = new Node();n->value = v++;n->next = NULL;if( slider == NULL ){slider = n;ret = n;}else{slider->next = n;slider = n;}}return ret;
}void destory_list(Node* list)
{while( list ){Node* del = list;list = list->next;delete del;}
}void print_list(Node* list)
{while( list ){cout << list->value << "->";list = list->next;}cout << "NULL" << endl;
}Node* merge(Node* list1, Node* list2)
{if( list1 == NULL ){return list2;}else if( list2 == NULL ){return list1;}else if( list1->value < list2->value ){return (list1->next = merge(list1->next, list2), list1);}else{return (list2->next = merge(list1, list2->next), list2);}
}int main()
{Node* list1 = create_list(1, 5);Node* list2 = create_list(2, 6);print_list(list1);print_list(list2);Node* list = merge(list1, list2);print_list(list);destory_list(list);return 0;
}

        运行结果如下

        我们看到经过合并后的链表如上图所示，都是由小到大的排序进行输出。

        6、汉诺塔问题：a> 将木块借助 B 柱由 A 柱移动到 C 柱；b> 每次只能移动一个木块；c> 只能出现小木块在大木块之上。如下

        下来我们将汉诺塔问题进行分解，将 n-1 个木块借助于 C 柱由 A 柱移动到 B 柱，将最底层的唯一木块直接移动到 C 柱，将 n-1 个木块借助 A 柱移动到 C 柱。如下图所示

        源码实现如下

#include <iostream>
#include <cstring>using namespace std;struct Node
{int value;Node* next;
};Node* create_list(int v, int len)
{Node* ret = NULL;Node* slider = NULL;for(int i=0; i<len; i++){Node* n = new Node();n->value = v++;n->next = NULL;if( slider == NULL ){slider = n;ret = n;}else{slider->next = n;slider = n;}}return ret;
}void destory_list(Node* list)
{while( list ){Node* del = list;list = list->next;delete del;}
}void print_list(Node* list)
{while( list ){cout << list->value << "->";list = list->next;}cout << "NULL" << endl;
}void HanoiTower(int n, char a, char b, char c)  // a ==> src  b ==> middle  c ==> dest
{if( n == 1 ){cout << a << "-->" << c << endl;}else{HanoiTower(n-1, a, c, b);HanoiTower(1, a, b, c);HanoiTower(n-1, b, a, c);}
}int main()
{HanoiTower(3, 'A', 'B', 'C');return 0;
}

        运行结果如下

        7、全排列问题，如下图所示

        源码实现如下

#include <iostream>
#include <cstring>using namespace std;struct Node
{int value;Node* next;
};Node* create_list(int v, int len)
{Node* ret = NULL;Node* slider = NULL;for(int i=0; i<len; i++){Node* n = new Node();n->value = v++;n->next = NULL;if( slider == NULL ){slider = n;ret = n;}else{slider->next = n;slider = n;}}return ret;
}void destory_list(Node* list)
{while( list ){Node* del = list;list = list->next;delete del;}
}void print_list(Node* list)
{while( list ){cout << list->value << "->";list = list->next;}cout << "NULL" << endl;
}void permutation(char* s, char* e)
{if( *s == '\0' ){cout << e << endl;}else{int len = strlen(s);for(int i=0; i<len; i++){swap(s[0], s[i]);permutation(s+1, e);swap(s[0], s[i]);}}
}int main()
{char s[] = "abc";permutation(s, s);return 0;
}

        我们来看看运行结果

        不过我们来看看字符串 “abc”的输出

        我们看到还是重复输出了。那么如果前面和后面每个字符是一样的，我们就不用进行递归了。优化后的源码如下

void permutation(char* s, char* e)
{if( *s == '\0' ){cout << e << endl;}else{int len = strlen(s);for(int i=0; i<len; i++){if( (i == 0) || (s[0] != s[i]) ){swap(s[0], s[i]);permutation(s+1, e);swap(s[0], s[i]);}}}
}

        运行结果如下

        通过对递归的学习，总结如下：1、递归是一种将问题分而自治的思想；2、用递归解决问题首先要建立递归的模型；3、递归解法必须要有边界条件，否则无解；4、不要陷入递归函数的执行细节，要学会通过代码描述递归问题。