[学习笔记]达内纪录片day06 递归思想

    选择打赏方式

关于递归,发下来的笔记上就那么寥寥数语,不过课堂上倒是讲了一下递归的设计思想。

递归,我个人的理解就是分而治之,逐层进入,逐层退出。

设计的时候,一定要有至少一个出口,否则会造成迭代。

其实,可以从高中数学的层面理解递归

如,计算有序数列求和:1+2+3+4+...+100

函数表达式为:

f(n)=f(n-1)+n

f(1)=1

数学中计算这道题,比如f(5)

计算步骤

f(5)=f(4)+5

f(4)=f(3)+4

f(3)=f(2)+3

f(2)=f(1)+2

f(1)=1

C语言实现代码如下:


#include <stdio.h>

int sum(int num) 
{
	if (num==1)
		return 1;

	return sum(num - 1) + num;
}


计算机就是这样算下去的,但是对于计算机来说,是不能直接计算f(5)=f(4)+5的,而是要先算出f(4),要算出f(4)就要先算出f(3),它会不停的自己调用自己,直到f(1),满足条件参数==1,返回1,这时候,调用它的函数f(2)=f(1)+2得到了f(1)返回的结果1,得以继续执行1+2,返回3,再次返回上一层call f(3)=f(2)+3,同时因为f2的结果3被返回,f(3)得以继续执行,并得到返回值6,再次返回上一层call f(4)=f(3)+4,返回10,最后返回最上层的call f(5)=f(4)+5,得到最终结果15。


递归原理演示:

void test(int num) 
{
	if (num == 1)
		printf("1\n");
	else
	{
		test(num - 1);
		printf("%d\n", num);
	}

}


调用一次后执行结果:

TIM截图20190707101602.png

交换else语句块下的test()函数和printf()函数位置:

TIM截图20190707101932.png


第二道例题

Fibonacci 数列

1 1 2 3 5 8 13 21

函数表达式:

fibonacci(n) = fibonacci(n-1)+fibonacci(n-2)

fibonacci(1) = 1

fibonacci(2) = 1

实现代码如下:

int febonacci(int n) 
{
	if (n <= 0)
		return 0;
	else if (n <= 2)
		return 1;
	else
		return febonacci(n - 1) + febonacci(n - 2);
}


数组元素排序:

设计思路和数列求和差不多,只不过这一次,我们需要的是最后一项和前面比出来的最大值作比较而已,出口是第0项,第0项的值一定是前0项的最大值,执行时逐层进入,再从参数为0的函数返回arr[0],然后逐层比较得出最大值,再逐层退出到最开始的那一层call。

实现代码:

int max_arr(int arr[],int n) 
{
	if (n <= 0)
		return arr[0];
	if (arr[n] > max_arr(arr, n - 1))
		return arr[n];
	else
		return max_arr(arr, n - 1);


}

THE END!


版权声明:若无特殊注明,本文皆为《 8964CN 》原创,转载请保留文章出处。
本文链接:[学习笔记]达内纪录片day06 递归思想 http://www.8964cn.net/?post=67
正文到此结束

热门推荐

发表吐槽

你肿么看?

你还可以输入 250 / 250 个字

嘻嘻 大笑 可怜 吃惊 害羞 调皮 鄙视 示爱 大哭 开心 偷笑 嘘 奸笑 委屈 抱抱 愤怒 思考 日了狗 胜利 不高兴 阴险 乖 酷 滑稽

评论信息框

吃奶的力气提交吐槽中...


既然没有吐槽,那就赶紧抢沙发吧!