基础算法 第4章 递归算法(C++版)-2022.01.27(C).pdf

递归算法 递归算法是C++语言程序设计中的一种重要方法，它使许多复杂的问题变得简单，容易解决了。递归特点是：函数或过程调用它自己本身。其中直接调用自己称为直接递归，而将A调用B，B以调用A的递归叫做间接递归。 1. 递归算法的定义 递归算法是指在函数或过程中调用自身的算法。递归算法可以将复杂的问题分解成更小的子问题，直到解决问题的基本情况为止。 2. 递归算法的特点 递归算法的特点是函数或过程调用它自己本身。递归算法可以分为直接递归和间接递归两种。直接递归是在A函数中嵌套使用A函数，而间接递归是在A函数中调用B函数，然后在B函数中调用A函数，实现递归。 3. 递归算法的应用 递归算法广泛应用于计算机科学和数学领域。例如，递归算法可以用于解决累加问题、查找问题、排序问题等。 4. 递归算法的优点 递归算法的优点是使问题变得简单、容易解决。递归算法可以将复杂的问题分解成更小的子问题，直到解决问题的基本情况为止。 5. 递归算法的缺点 递归算法的缺点是其计算复杂度高、占用系统资源多。递归算法也容易出现栈溢出错误。 6. 递归算法的实现 递归算法的实现需要遵守三个基本条件： （1）问题可以分解成更小的子问题。 （2）每个子问题的解可以用与原问题相同的方法解决。 （3）存在一个基本情况，可以终止递归调用。 例如，计算1+2+3+4+…+(n-1)+n的递归算法可以用以下公式表示： s(n) = s(n-1) + n 其中，s(n)是从1到n的累加和。 7. 递归算法的例子 例1：计算1+2+3+4+…+(n-1)+n的递归算法。 ``` #include<iostream> using namespace std; int fac(int); int main(void) { int t; cin >> t; cout << "s=" << fac(t) << endl; } int fac(int n) { if (n == 1) return 1; return (fac(n-1) + n); } ``` 例2：二分查找递归算法。 ``` #include<iostream> #include<cstdlib> using namespace std; int a[11]; void search(int,int,int); int main() { int k,x,L=1,R=10; cout << "输入10个从大到小顺序的数：" << endl; for (k=1;k<=10;k++) cin >> a[k]; cin >> x; search(x,L,R); system("pause"); } void search(int x,int top,int bot) { int mid = (top + bot) / 2; if (x == a[mid]) { cout << "YES" << endl; } else if (x < a[mid]) { search(x,top,mid-1); } else { search(x,mid+1,bot); } } ``` 递归算法是一种重要的算法设计方法，广泛应用于计算机科学和数学领域。递归算法可以将复杂的问题分解成更小的子问题，直到解决问题的基本情况为止。但是，递归算法也存在计算复杂度高、占用系统资源多的缺点。