递归(一)几个简单的递归例子

妖狐艹你老母 2022-05-26 09:30 155阅读 0赞

###### 刚接触递归的同学，可能难以理解递归，难以理解的点可能很多，例如： ######

1.函数为什么可以在自己的内部又调用自己呢?

2.既然可以自己调用自己，那么递归运行过程中一定回有很多层相互嵌套，到底什么时候不再嵌套呢？

3.递归运行过程中，相互嵌套的多层之间会有参数传递，多层之间是否会相互影响？

递归两个要素

1.递归边界

2.递归的逻辑——递归"公式"

递归的过程一定有参数的变化，并且参数的变化，和递归边界有关系.

在难度较大的题目中，这两者均不容易直接得到.

递归的种种问题，也许理解的同学可能可以用一句话解释清楚，但是不理解的同学再怎么说也没办法理解.

下面通过几个简单的例子【体会】一下递归，先从【感性】的角度理解递归.

1.Fibonacci数

我们直到Fibonacci数的递推公式为：F(0)=F(1)=1,F(n)=F(n-1)+F(n-2) n>=2;

这个明显地给出了递归边界n=0或1的时候F(n)的值，和递归逻辑F(n)=F(n-1)+F(n-2)，即递推公式.所以这个递归函数不难书写

\[cpp\] [view plain][] [copy][view plain]

1.  \#include<iostream>
2.  **using****namespace** std; 
3.  
4.  **int** F(**int** n)//函数返回一个数对应的Fibonacci数
5.  \{ 
6.  **if**(n==0 || n==1)//递归边界
7.  **return** 1; 
8.  **return** F(n-1) + F(n-2);//递归公式
9.  \} 
10. 
11. **int** main() 
12. \{ 
13. //测试
14. **int** n; 
15. **while**(cin >> n) 
16.  cout << F(n) << endl; 
17. 
18. **return** 0; 
19. \}

2.阶乘

阶乘的递归公式为：

![Center][]

代码如下：

\[cpp\] [view plain][] [copy][view plain]

1.  \#include<iostream>
2.  **using****namespace** std; 
3.  
4.  **int** F(**int** n) 
5.  \{ 
6.  **if**(n==0)//递归边界
7.  **return** 1; 
8.  
9.  **return** n\*F(n-1);//递归公式
10. \} 
11. 
12. **int** main() 
13. \{ 
14. **int** n; 
15.  cin >> n; 
16.  cout << F(n) << endl; 
17. 
18. **return** 0; 
19. \}

3.数组求和

给一个数组a\[\]:a\[0\],a\[1\],...,a\[n-1\]如何用递归的方式求和？

仍然是两个问题：递归边界和递归公式.

递归边界是什么？一时不容易想到，但是我们想到了求和，多个数的求和过程是什么，x,y,z,w手动求和的过程是什么？步骤如下：

x+y=a,任务变为a,z,w求和

a+z=b,任务变为b,w求和

b+w=c得出答案

思考一下，【得出答案】这一步为什么就可以得出答案呢？(废话？)是因为，一个数不用相加就能得出答案.

所以，递归的边界就是只有一个数.

所以，递归边界有了，那么递归公式呢？其实手动计算过程中，隐含了递归公式：

![Center 1][]

其中+为求两个数的和，F为求多个数的和的递归函数.代码如下：

\[cpp\] [view plain][] [copy][view plain]

1.  \#include<iostream>
2.  **using****namespace** std; 
3.  
4.  **int** F(**int** a\[\],**int** start,**int** end) 
5.  \{ 
6.  **if**(start==end)//递归边界
7.  **return** a\[start\]; 
8.  
9.  **return** a\[start\] + F(a,start+1,end);//递归公式
10. \} 
11. 
12. **int** main() 
13. \{ 
14. **int** a\[\] = \{1,2,3,4,5\}; 
15. **int** s=0,e=4; 
16.  cout << F(a,s,e) << endl; 
17. 
18. **return** 0; 
19. \}

4.求数组元素最大值

手动求最大值的过程是什么，遍历+比较，过程如下：

例如，求3,2,6,7,2,4的最大值：先设置最大值max=-999999，然后将max和数组元素逐个(遍历)比较如果a\[i\]>max，则更新max的值为a\[i\]，否则max不变，继续向后遍历，直到遍历结束.

max<3，则max=3

max>2，max=3不变

max<6，则max=6

max<7，则max=7

max>2，max=7不变

max>4，max=7不变

遍历结束，max=7为最大值.

和求和类似，递归的公式如下：

![Center 2][]

其中max为求两个数的较大值函数，F为求多个数的最大值的递归函数.代码如下：

\[cpp\] [view plain][] [copy][view plain]

1.  \#include<iostream>
2.  **using****namespace** std; 
3.  
4.  \#define max(a,b) (a>b?a:b)
5.  
6.  **int** F(**int** a\[\],**int** s,**int** e) 
7.  \{ 
8.  **if**(s==e) 
9.  **return** a\[s\]; 
10. **else****if**(s+1 == e)//递归边界
11. **return** max(a\[s\],a\[e\]); 
12. 
13. **return** max(a\[s\],F(a,s+1,e));//递归公式!!!
14. \} 
15. 
16. **int** main() 
17. \{ 
18. **int** a\[\] = \{5,1,4,6,2\}; 
19. **int** s = 0,e = 4; 
20.  cout << F(a,s,e) << endl; 
21. 
22. **return** 0; 
23. \}

之所以，说上面的几个例子是【简单例子】，是因为上述所有的递归都属于【单向递归】.单向递归，递归的路径就是一个方向，所以思路相对比较容易想到.

较难的递归问题，一般都不是单向递归，而是需要使用【回溯】的方法，递归的方法不太容易想到

[view plain]: https://blog.csdn.net/ten_sory/article/details/64126341#
[Center]: /images/20220526/69ce40587b9543d1ba83c6271dbf5bfd.png
[Center 1]: /images/20220526/3d5631b8ee2e4b1a8a6e61a222aa00f1.png
[Center 2]: /images/20220526/c88438e7ad8e4bfdb112f16366c0797c.png