第二章 递归法
::: hljs-center
目录
●第二章 递归法
●前言
●一、递归法是什么？
1.简要介绍
2.生活实例
●二、递归法的典型案例——阶乘函数&斐波那契数列
1.阶乘函数
2.斐波那契数列
●总结 :::
前言
简单的来说，算法就是用计算机程序代码来实现数学思想的一种方法。学习算法就是为了了解它们在计算机中如何演算，以及在当今的信息时代，它们是如何在各个层面上影响我们的日常生活的，从而提高我们的逻辑思维能力和处理实际问题的能力。善用算法、巧用算法，是培养程序设计逻辑的重中之重，许多实际的问题都可用多个可行的算法来解决， 但是要从中找出最优的解决算法却是一项挑战。
一、递归法是什么？
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();
}
④ 代码结果展示
总结
在上面，我们通过一个生活中的实例以及两个递归的典型问题，去详细的分析了递归法的核心思想和在程序中的具体实现过程。从程序设计语言的角度来说，谈到递归的定义，可以这样来描述：假如一个函数或子程序是由它自身所定义或调用的，就称它为递归。它至少要定义两个条件，一个是可以反复执行的递归过程，另一个是跳出执行过程的出口。
<您的三连和关注是我最大的动力> ???? 文章作者：Keanu Zhang 分类专栏：算法之美（C++系列文章）