第二章 递归法
前言
简单的来说，算法就是用计算机程序代码来实现数学思想的一种方法。学习算法就是为了了解它们在计算机中如何演算，以及在当今的信息时代，它们是如何在各个层面上影响我们的日常生活的，从而提高我们的逻辑思维能力和处理实际问题的能力。善用算法、巧用算法，是培养程序设计逻辑的重中之重，许多实际的问题都可用多个可行的算法来解决， 但是要从中找出最优的解决算法却是一项挑战。
一、递归法是什么？
1.简要介绍
递归是一种很特殊的算法，分治法和递归法它们共同运用到一种思想，就是都将一个复杂的算法问题进行分解，让其变成一个个规模越来越小的子问题从而进行解决。简单来说，在程序设计语言中，函数或子程序不只是能够被其他函数调用或引用，还可以去自己调用自己，这就是所谓的递归。递归在早期人工智能所用的语言中是整个语言运行的核心，C/C++、Java、Python等很多程序设计语言都具备递归功能。
2.生活实例
① 我们和朋友两人去看电影，由于没有相邻的座位两人就各自买了票。但是我因为需要去上厕所将自己的票给了朋友，并且他先进场了。我来到放映厅中由于没有电影票而不知道自己的位置，而我们朋友的座位在某一排的最里面，所以这时我们就需要让这排最左边的这个人向里面传话，而他的右边不是我们的那个朋友就继续传话...... 直到传到我们的朋友那里，然后他在把电影票从最里面一个个传到外面，直到传到我们的手上。这个生活中常见的例子，就很像我们所要学习的递归法。
二、递归法的典型案例——阶乘函数&斐波那契数列
1.阶乘函数
①具体情况：（公式+实例）
公式直接实现以及在程序代码中的实现过程
②递归调用算法代码段：
int recursive(int n) { int sum; if (n == 1) //终止递归的条件，跳出递归过程的出口 return 1; else return sum=n * recursive(n - 1); //sum=n*(n-1)!,直接去调用自己，反复递归过程 }
③ 代码展示（C++）
实现案例：用递归算法去求解阶乘10的值。
#include<iostream> using namespace std; class digui { public: long long fact(int x) { if (x == 1) { return result = 1; } else { return result = x * fact(x - 1); } } void showresult() { cout << result << endl; } int a; long long result; }; void func() { digui dg; cout << "请输入要求解的递归数："; cin >> dg.a; dg.fact(dg.a); dg.showresult(); } int main() { func(); }
④ 代码结果展示：
2.斐波那契数列
①具体情况（公式+实例）
公式直接实现以及在程序代码中的实现过程
②递归调用算法代码段：
int Fib(int n) { if (n == 1 || n == 2) return 1; else return Fib(n - 1) + Fib(n-2); } ③ 代码展示（C++） 实现案例：用递归算法去求第10个斐波那契数。 #include<iostream> using namespace std; class digui { public: int fibonacci(int x) { int m, n; if (x == 1 || x == 2) { return num = 1; } else { m = fibonacci(x - 1); n = fibonacci(x - 2); return num = m + n; } } void shownum() { cout << num << endl; } int a; int num; }; void text() { digui dg; cout << "输入你要求的第几个斐波那契数："; cin >> dg.a; dg.fibonacci(dg.a); dg.shownum(); } int main() { text(); }
④ 代码结果展示：
总结
在上面，我们通过一个生活中的实例以及两个递归的典型问题，去详细的分析了递归法的核心思想和在程序中的具体实现过程。从程序设计语言的角度来说，谈到递归的定义，可以这样来描述：假如一个函数或子程序是由它自身所定义或调用的，就称它为递归。它至少要定义两个条件，一个是可以反复执行的递归过程，另一个是跳出执行过程的出口。
