递归 ╰半橙微兮° 2022-06-09 09:14 314阅读 0赞 递归算法基本思想：找出递归子结构性质（原问题的解包含了子问题的解）、用子问题的解来递归定义原问题的解、找出递归终止条件。 ## 示例： ## ### 例1 阶乘函数 ### 阶乘函数可递归地定义为： n! = 1 n = 0 (边界条件) n! = n(n-1)! n > 0 (递归方程) 边界条件与递归方程是递归函数的二个要素，递归函数只有具备了这两个要素，才能在有限次计算后得出结果。 实现： ![复制代码][copycode.gif] /* 主题：阶乘使用递归和非递归实现 * 作者：chinazhangjie * 邮箱：chinajiezhang@gmail.com * 开发语言：C++ * 开发环境：Code::Blocks 10.05 * 时间: 2010.10.05 */ #include < iostream > using namespace std; // factorial implement by recursive long factorial_recursive( long n) { if (n == 0 ) return 1 ; return n * factorial_recursive(n - 1 ); } // factorial implement by loop long factorial_loop( long n) { long result = 1 ; for ( int i = n; i > 0 ; -- i) result *= i; return result; } int main() { for ( int i = 0 ; i < 10 ; i ++ ) { cout << i << " ! " << " = " << factorial_recursive(i) << " , " << factorial_loop(i) << endl; } return 0 ; } ![复制代码][copycode.gif] ### 例2 Fibonacci数列 ### 无穷数列1，1，2，3，5，8，13，21，34，55，……，称为Fibonacci数列。它可以递归地定义为： F(n) = 1 n = 0 (边界条件) F(n) = 1 n = 1 (递归方程) F(n) = F(n - 1) + F(n - 2) n > 2 (递归方程) 实现： ![复制代码][copycode.gif] /* 主题：fibonacci数列使用递归和非递归实现 * 作者：chinazhangjie * 邮箱：chinajiezhang@gmail.com * 开发语言：C++ * 开发环境：Code::Blocks 10.05 * 时间: 2010.10.05 */ #include < iostream > using namespace std; // fibonacci implement by recursive long fibonacci_recursive( long n) { if (n <= 1 ) return 1 ; return fibonacci_recursive(n - 1 ) + fibonacci_recursive(n - 2 ); } // fibonacci implement by loop long fibonacci_loop( long n) { if (n == 0 || n == 1 ) return 1 ; long f1 = 1 ; long f2 = 1 ; long result = 0 ; for ( long i = 1 ; i < n ; ++ i) { result = f1 + f2; f1 = f2; f2 = result; } return result; } int main() { cout << " fibonacci implement by recursive: " << endl; for ( long i = 0 ; i <= 20 ; ++ i) cout << fibonacci_recursive(i) << " " ; cout << endl << endl; cout << " fibonacci implement by loop: " << endl; for ( long i = 0 ; i <= 20 ; ++ i) cout << fibonacci_loop(i) << " " ; cout << endl; return 0 ; } ![复制代码][copycode.gif] 例3 Ackerman函数 当一个函数及它的一个变量是由函数自身定义时，称这个函数是双递归函数。 Ackerman函数A(n，m)定义如下： A(1,0) = 2 A(0,m) = 1 m >= 0 A(n,0) = n + 2 n >= 2 A(n,m) = A(A(n-1,m),m-1) n,m >= 1 前2例中的函数都可以找到相应的非递归方式定义： n! = 1 \* 2 \* 3 \* ... \* (n - 1) \* n ![2010100711411138.jpg][] 本例中的Ackerman 函数却无法找到非递归的定义。 A(n，m)的自变量m的每一个值都定义了一个单变量函数： M = 0时，A(n,0)=n+2 M = 1时，A(n,1)=A(A(n-1,1),0) = A(n-1,1)+2，和 A(1,1)=2故A(n,1)=2\*n M = 2时，A(n,2) = A(A(n-1,2),1)=2A(n-1,2)，和A(1,2)=A(A(0,2),1)=A(1,1)=2，故A(n,2)= 2^n 。 M = 3时，类似的可以推出![2010100711415747.jpg][] M = 4时，A(n,4) 的增长速度非常快，以至于没有适当的数 学式子来表示这一函数。 实现： ![复制代码][copycode.gif] /* 主题：ackerman函数使用递归实现 * 作者：chinazhangjie * 邮箱：chinajiezhang@gmail.com * 开发语言：C++ * 开发环境：Code::Blocks 10.05 * 时间: 2010.10.05 */ #include < iostream > using namespace std; // ackerman implement long ackerman( long n, long m) { if (n == 1 && m == 0 ) return ( long ) 2 ; if (n == 0 ) return 1 ; if (m == 0 ) return n + 2 ; return ackerman( ackerman(n - 1 ,m) , m - 1 ); } int main() { cout << " m = 0 : " << endl; cout << " ackerman(1,0) = " << ackerman( 1 , 0 ) << endl; cout << " ackerman(2,0) = " << ackerman( 2 , 0 ) << endl; cout << " ackerman(3,0) = " << ackerman( 3 , 0 ) << endl; cout << " ackerman(4,0) = " << ackerman( 4 , 0 ) << endl; cout << " m = 1 : " << endl; cout << " ackerman(1,1) = " << ackerman( 1 , 1 ) << endl; cout << " ackerman(2,1) = " << ackerman( 2 , 1 ) << endl; cout << " ackerman(3,1) = " << ackerman( 3 , 1 ) << endl; cout << " ackerman(4,1) = " << ackerman( 4 , 1 ) << endl; cout << " m = 2 : " << endl; cout << " ackerman(1,2) = " << ackerman( 1 , 2 ) << endl; cout << " ackerman(2,2) = " << ackerman( 2 , 2 ) << endl; cout << " ackerman(3,2) = " << ackerman( 3 , 2 ) << endl; cout << " ackerman(4,2) = " << ackerman( 4 , 2 ) << endl; cout << " m = 3 : " << endl; cout << " ackerman(1,3) = " << ackerman( 1 , 3 ) << endl; cout << " ackerman(2,3) = " << ackerman( 2 , 3 ) << endl; cout << " ackerman(3,3) = " << ackerman( 3 , 3 ) << endl; cout << " ackerman(4,3) = " << ackerman( 4 , 3 ) << endl; return 0 ; } ![复制代码][copycode.gif] 例4 排列问题 设计一个递归算法生成n个元素\{r1,r2,…,rn\}的全排列。 设R=\{r1,r2,…,rn\}是要进行排列的n个元素， Ri=R-\{ri\} 。 集合X中元素的全排列记为perm(X)。 (ri)perm(X)表示在全排列perm(X)的每一个排列前加上前缀得到的排列。R的全排列可归纳定义如下： 当n=1时，perm(R)=(r)，其中r是集合R 中唯一的元素； 当n>1时，perm(R)由(r1)perm(R1)，(r2)perm(R2)，…，(rn)perm(Rn)构成。 ![复制代码][copycode.gif] /* 主题：全排列使用递归和非递归实现 * 作者：chinazhangjie * 邮箱：chinajiezhang@gmail.com * 开发语言：C++ * 开发环境：Code::Blocks 10.05 * 时间: 2010.10.07 */ #include < iostream > #include < vector > #include < iterator > using namespace std; /* 使用递归实现 * 递归产生所有前缀是list[0:k-1]， * 且后缀是list[k,m]的全排列的所有排列 * 调用算法perm(list,0,n-1)则产生list[0:n-1]的全排列 */ template < class T > void perm_recursion(T list[], int k, int m) { // 产生list[k:m]的所有排列 if (k == m) { for ( int i = 0 ; i <= m; i ++ ) cout << list[i] << " " ; cout << endl; } else { // 还有多个元素，递归产生排列 for ( int i = k; i <= m; ++ i) { swap(list[k],list[i]); perm_recursion(list,k + 1 ,m); swap(list[k],list[i]); } } } // 非递归实现（可参照STL next_permutation源码） template < class T > void perm_loop(T list[], int len) { int i,j; vector < int > v_temp(len); // 初始排列 for (i = 0 ; i < len ; i ++ ) v_temp[i] = i; while ( true ) { for (i = 0 ; i < len; i ++ ) cout << list[v_temp[i]] << " " ; cout << endl; // 从后向前查找，看有没有后面的数大于前面的数的情况，若有则停在后一个数的位置。 for (i = len - 1 ;i > 0 && v_temp[i] < v_temp[i - 1 ] ; i -- ); if (i == 0 ) break ; // 从后查到i，查找大于 v_temp[i-1]的最小的数，记入j for (j = len - 1 ; j > i && v_temp[j] < v_temp[i - 1 ] ; j -- ); // 交换 v_temp[i-1] 和 v_temp[j] swap(v_temp[i - 1 ],v_temp[j]); // 倒置v_temp[i]到v_temp[n-1] for (i = i,j = len - 1 ; i < j;i ++ ,j -- ) { swap(v_temp[i],v_temp[j]); } } } int main() { int list[] = { 0 , 1 , 2 }; cout << " permutation implement by recursion: " << endl; perm_recursion(list, 0 , 2 ); cout << endl; cout << " permutation implement by loop: " << endl; perm_loop(list, 3 ); cout << endl; return 0 ; } ![复制代码][copycode.gif] 例5 整数划分问题 将正整数n表示成一系列正整数之和：n=n1+n2+…+nk，其中n1≥n2≥…≥nk≥1，k≥1。 正整数n的这种表示称为正整数n的划分。正整数n的不同划分个数称为正整数n的划分数，记作p(n)。 例如正整数6有如下11种不同的划分，所以p(6) = 11： 6； 5+1； 4+2，4+1+1； 3+3，3+2+1，3+1+1+1； 2+2+2，2+2+1+1，2+1+1+1+1； 1+1+1+1+1+1。 前面的几个例子中，问题本身都具有比较明显的递归关系，因而容易用递归函数直接求解。 在本例中，如果设p(n)为正整数n的划分数，则难以找到递归关系，因此考虑增加一个自变量：在正整数n的所有不同划分中，将最大加数n1不大于m的划分个数记作q(n,m)。可以建立q(n,m)的如下递归关系。 (1) q(n,1)=1,n >= 1;当最大加数n1不大于1时，任何正整数n只有一种划分形式， 即n = 1 + 1 + 1 + … +1. (2) q(n,m) = q(n,n),m >= n; 最大加数n1实际上不能大于n。因此，q(1,m)=1。(3) q(n,n)=1 + q(n,n-1); 正整数n的划分由n1=n的划分和n1 ≤ n-1的划分组成。 (4) q(n,m)=q(n,m-1)+q(n-m,m),n > m >1;正整数n的最大加数n1不大于m的划分由 n1 = m的划分和n1 ≤ m-1 的划分组成。 前面的几个例子中，问题本身都具有比较明显的递归关系，因而容易用递归函数直接求解。 在本例中，如果设p(n)为正整数n的划分数，则难以找到递归关系，因此考虑增加一个自变量：将最大加数n1不大于m的划分个数记作q(n,m)。可以建立q(n,m)的如下递归关系。 q(n,m) = 1 n = 1, m = 1 q(n,m) = q(n,n) n = 1, m = 1 q(n,m) = 1 + q(n,n-1) n = m q(n,m) = q(n,m-1) + q(n-m,m) n > m > 1 正整数n的划分数p(n) = q(n,n)。 实现： ![复制代码][copycode.gif] /* 主题：整数划分使用递归实现 * 作者：chinazhangjie * 邮箱：chinajiezhang@gmail.com * 开发语言：C++ * 开发环境：Code::Blocks 10.05 * 时间: 2010.10.07 */ #include < iostream > using namespace std; // int __int_partition( int n, int m) { if (n < 1 || m < 1 ) return 0 ; if (n == 1 || m == 1 ) return 1 ; if (n < m) return __int_partition(n,n); if (n == m) return __int_partition(n,m - 1 ) + 1 ; return __int_partition(n,m - 1 ) + __int_partition(n - m,m); } int integer_partition( int n) { return __int_partition(n,n); } int main() { for ( int i = 1 ; i < 7 ; ++ i) { cout << " integer_patition( " << i << " ) = " << integer_partition(i) << endl; } return 0 ; } ![复制代码][copycode.gif] 例6 Hanoi塔问题 设a,b,c是3个塔座。开始时，在塔座a上有一叠共n个圆盘，这些圆盘自下而上，由大到小地叠在一起。各圆盘从小到大编号为1,2,…,n,现要求将塔座a上的这一叠圆盘移到塔座b上，并仍按同样顺序叠置。在移动圆盘时应遵守以下移动规则： 规则1：每次只能移动1个圆盘； 规则2：任何时刻都不允许将较大的圆盘压在较小的圆盘之上； 规则3：在满足移动规则1和2的前提下，可将圆盘移至a,b,c中任一塔座上。 ![2010100716242714.jpg][] 实现： ![复制代码][copycode.gif] /* 主题：hanoi使用递归实现 * 作者：chinazhangjie * 邮箱：chinajiezhang@gmail.com * 开发语言：C++ * 开发环境：Code::Blocks 10.05 * 时间: 2010.10.07 */ #include < iostream > using namespace std; void __move( char t1, char t2) { cout << t1 << " -> " << t2 << endl; } // 把n个圆盘，从t1塔移至t2塔通过t3塔 void hanoi( int n, char t1, char t2, char t3) { if (n > 0 ) { hanoi(n - 1 ,t1,t3,t2); __move(t1,t2); hanoi(n - 1 ,t3,t2,t1); } } int main() { cout << " hanoi(1,'a','b','c'): " << endl; hanoi( 1 , ' a ' , ' b ' , ' c ' ); cout << endl; cout << " hanoi(1,'a','b','c'): " << endl; hanoi( 2 , ' a ' , ' b ' , ' c ' ); cout << endl; cout << " hanoi(3,'a','b','c'): " << endl; hanoi( 3 , ' a ' , ' b ' , ' c ' ); cout << endl; return 0 ; } ![复制代码][copycode.gif] 递归小结 优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。 缺点：递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。 解决方法：在递归算法中消除递归调用，使其转化为非递归算法。 1、采用一个用户定义的栈来模拟系统的递归调用工作栈。该方法通用性强，但本质上还是递归，只不过人工做了本来由编译器做的事情，优化效果不明显。 2、用递推来实现递归函数。 3、通过变换能将一些递归转化为尾递归，从而迭代求出结果。 后两种方法在时空复杂度上均有较大改善，但其适用范围有限。 [copycode.gif]: /images/20220609/621ab9193eaa42afbfdddefd4ec24a9c.png [2010100711411138.jpg]: /images/20220609/e17ef32d94c24d31865f159bd204f62b.png [2010100711415747.jpg]: /images/20220609/daefa81fd2494282b1f06bc69cc7d05e.png [2010100716242714.jpg]: /images/20220609/4a541baf1de24d4191a76dcdc0bbdda8.png
相关 递归---从台阶问题学习递归、递归优化和非递归 > 递归就是将大问题划分为若干个子问题，各个问题是嵌套关系，最小的那个问题的结果是已知的，大问题不断分解直到达到最小问题的过程叫做“递”，小问题的解释已知的，然后根据这个解回过 电玩女神/ 2023年06月17日 06:57/ 0 赞/ 36 阅读
相关 递归 include<iostream> include<cmath> using namespace std; const int Len = 66 - 日理万妓/ 2022年06月12日 01:41/ 0 赞/ 83 阅读
相关 递归 递归算法基本思想：找出递归子结构性质（原问题的解包含了子问题的解）、用子问题的解来递归定义原问题的解、找出递归终止条件。 示例： 例1 阶乘函数 阶乘函数可 ╰半橙微兮°/ 2022年06月09日 09:14/ 0 赞/ 315 阅读
相关 递归——线性递归与二分递归 递归 线性递归 例子1：数组求和 int sum( int A[], int n) { //数组求和算法：线性递归版 if 向右看齐/ 2022年05月21日 04:41/ 0 赞/ 357 阅读
相关 递归 递归优点：代码简单 代码量少 递归缺点：不易理解 用递归解决问题时，主要思路： 1.将一个大问题分解成子问题 2.子问题除了问题规模会变小，和原问题解决的思路是一 向右看齐/ 2022年05月03日 10:28/ 0 赞/ 238 阅读
相关 递归 1. public class HelloWorld \{ 2. public static void main(String\[\] args)\{ 3. // Sca 女爷i/ 2022年04月12日 10:50/ 0 赞/ 360 阅读
相关 递归 递归Recursion 递归要求 1. 递归一定要有退出条件，递归调用一定要执行到这个退出条件。没有退出条件的递归调用，就是无限调用 2 雨点打透心脏的1/2处/ 2022年02月19日 05:39/ 0 赞/ 328 阅读
相关 递归 问题描述 任何一个正整数都可以用2进制表示，例如：137的2进制表示为10001001。 将这种2进制表示写成2的次幂的和的形式，令次幂高的排在前面，可得到如下表达式：13 冷不防/ 2021年12月24日 08:43/ 0 赞/ 334 阅读
相关 递归 递归 递归就是一个函数直接或间接的调用自己.一般来说,递归需要有边界条件,递归前进段和递归返回段.当边界条件不满足的时,递归前进,当边界条件满足的时候,递归返回. 递归就 ﹏ヽ暗。殇╰゛Y/ 2021年12月12日 06:53/ 0 赞/ 263 阅读
相关 递归 递归只是让你解决方案更加清晰，并没有性能上的优势。实际上，在有些情况下，使用循环的性能更好。正如，在Stack Overflow 上，Leigh Caldwell 说了一句话： 男娘i/ 2021年09月13日 23:58/ 0 赞/ 392 阅读
电玩女神
向右看齐
还没有评论，来说两句吧...