递归算法和分治法总结（典型算法思想与应用4）

递归算法（Recursion method）是函数根据递归条件不断调用自身并在一定条件下返回的方法，这样的函数称为递归函数。编译器在函数调用时会维护一个内存栈，一次函数调用会生成一个函数栈帧，在栈帧中保存有返回地址址，一些寄存器的原始值和更新值、参数值、中间变量，这些值依次压栈，并在函数返回时逆序依次弹出。递归函数的依次调用会依次建立栈帧，每个函数栈帧的参数（如果有）一般会形成一个迭代关系。而递归函数本身也可以在相互递推、递归返回中形成一个迭代关系。

递归法也有分治法的思想，子问题之间是同类、纵向的关系。（枚举法的子问题之间是横向的关系）

一般来讲，递归需要有边界条件、递归前进段和递归返回段。当边界条件不满足时，递归前进，当边界条件满足时，递归返回。在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。

在计算机编程应用中，递归算法对解决大多数问题是十分有效的，它能够使算法的描述变得简洁而且易于理解。递归算法有如下3 个特点。

① 递归过程一般通过函数或子过程来实现。

② 递归算法在函数或子过程的内部，直接或者间接地调用自己的算法。

③ 递归算法实际上是把问题转化为规模缩小了的同类问题的子问题，然后再递归调用函数或过程来表示问题的解。子函数相对于其递归函数，问题性质相同（解决问题的步骤），规模较小。

在使用递归算法时，应该注意如下4 点。

① 递归是在过程或函数中调用自身的过程。

② 在使用递归策略时，首先要确定递归表达式，然后必须有一个明确的递归结束条件，这称为递归出口。

③ 递归算法通常显得很简洁，但是运行效率较低，所以一般不提倡用递归算法设计程序。

④ 在递归调用过程中，系统用栈来存储每一层的返回点和局部量。如果递归次数过多，则容易造成栈溢出，所以一般不提倡用递归算法设计程序。

⑤ 理解递归首先要较深入理解编译器调用函数、使用内存栈，压参数、参数迭代、以及保存返回值或返回值地址到寄存器，弹栈，返回值或地址值的一整个流程。

⑥ 理解递归的另一个重点要理解函数递归了n次，这n份代码的执行流程，在每份递归函数代码中，以递归语句为基准，前面的语句由递推阶段执行，后面的语句在递推返回阶段执行（如果是尾递归，这部分没有），递归语句本身作为函数调用和值返回（如果有的话）。

因为递归算法思想往往用函数的形式来体现，所以递归算法需要预先编写功能函数。这些函数是独立的功能，能够实现解决某个问题的具体功能，当需要时直接调用这个函数即可。递归函数的一般格式：

if(边界条件1成立) { 赋予边界值1 } else if(边界条件2成立) { 赋予边界值2 } else { 调用递归表达式 }

递归应用的实例随处可见，如阶乘、汉诺塔问题、斐波那契数列问题、快速排序、二分查找等。

对于尾递归（递归语句后还有代码），如阶乘，通常较容易转化为循环来解决，非尾递归（递归语句后没有代码了），如汉诺塔问题，用循环解决往往较复杂，需要另外使用一个栈的数据结构。

二分查找问题可以用递归解决，代码看起来很简洁，也可以用循环解决，效率较高：

// 递归有自调用的问题，需要将start和end写在参数列表中 // 来标记和动态变更搜索范围的开始和结束 int bisoRecurs(int arr[], int findData, int start, int end) { if(arr==NULL || start>end) return -1; int mid = start (end-start)/2; if(arr[mid] == findData) return mid; else if(findData < arr[mid]) bisoRecurs(arr, findData, start, mid-1); // 参数迭代 end = mid-1且有压栈 else bisoRecurs(arr, findData, mid 1, end); // 参数迭代 start = mid-1且有压栈 }

递归算法的代码之所以简洁，是因为其复杂性由编译器完成了，由编译器自动维护的内存栈，并自动完成入栈和出栈的工作。

递归函数与其子函数两者的性质完全相同，区别只在于子函数的规模较小，所以是分治法的一种体现。且因上述的自动递归调用与返回，且在调用之间函数参数实现了迭代，所以其应用非常广泛（C ｜18个使用递归的实例）。但其弊端也正在如此，函数的调用会带来空间和时间效率方面的损耗。

在典型算法思想与应用2｜迭代法与近似求函数值和最大公约数问题一文中有提到用二分法和迭代法解决求平方根问题，自然用递归也行：

double squareRoot(double a, double x0) // 13 求平方根 { double ans; double x1=(x0 a/x0)/2; if(fabs(x1-x0)>1e-8) ans = squareRoot(a,x1); else ans=x1; return ans; }

仔细想了一下，说递归如果不贴一下汉诺塔问题的代码，似乎不完整（因为此问题用循环写需要栈来辅助，写起来非常繁杂，而递归实现虽然其编译器内部复杂，还有重复求值的问题，但代码简洁）：

void hanoi(int n, char from, char temp, char to) // 16 汉诺塔 { if (n==1) printf("%c→%c(1)\n",from,to); else { hanoi(n-1,from,to,temp); //将x上编号为1到n-1的圆盘移到y，z作辅助塔 printf("%c→%c\n",from,to); //将x上编号为n的圆盘移到z hanoi(n-1,temp,from,to); //将y上编号为1到n-1的圆盘移到z，y作辅助塔 } } void main16() { hanoi(3,'A','B','C'); cin.get(); } /* A→C(1) A→B C→B(1) A→C B→A(1) B→C A→C(1) */

附二分查找的递归与非递归实现

#include<iostream> // 二分查找的递归与非递归实现 using namespace std; // 分治法，可分，可合，子问题有独立性 int bisoLoop(int arr[], int len, int findData) { if(arr==NULL || len <=0) return -1; int start = 0; int end = len-1; while(start<=end) { int mid = start (end-start)/2; if(arr[mid] == findData) return mid; else if(findData < arr[mid]) end = mid-1; else start = mid 1; } return -1; } // 递归有自调用的问题，需要将start和end写在参数列表中 // 来标记和动态变更搜索范围的开始和结束 int bisoRecurs(int arr[], int findData, int start, int end) { if(arr==NULL || start>end) return -1; int mid = start (end-start)/2; if(arr[mid] == findData) return mid; else if(findData < arr[mid]) bisoRecurs(arr, findData, start, mid-1); else bisoRecurs(arr, findData, mid 1, end); } void main() { int arr[] = {1,2,3,4,5,6,7,8}; int len = sizeof(arr)/sizeof(arr[0]); int index = bisoLoop(arr,len,6); int index2 = bisoRecurs(arr,6,0,len-1); cout<<index<<endl; cout<<index2<<endl; system("pause"); } /* 5 5 */

－End－