国外字体设计网站,常用网站开发技术和工具,seo外包 杭州,什么是百度指数目录
一、定义 1.概述 2.条件 3.比较
二、 如何理解递归#xff1f; 1.函数调用其他函数示例 : 2.函数调用函数自身示例 : 3.函数调用自身的底层操作 : ①在主调函数调用被调函数之前—— ②在被调函数返回主调函数之前—— ③在出现多个函数相互调用的情况时——
三、递…目录
一、定义 1.概述 2.条件 3.比较
二、 如何理解递归 1.函数调用其他函数示例 : 2.函数调用函数自身示例 : 3.函数调用自身的底层操作 : ①在主调函数调用被调函数之前—— ②在被调函数返回主调函数之前—— ③在出现多个函数相互调用的情况时——
三、递归的具体实例 1.求1~100的和 : 思路 : 代码 : 优化 : 2. 汉诺塔问题 : 背景 : 思路 : 代码 : 3.斐波那契数 : 介绍 : 思路 : 代码 : 一、定义 1.概述 递归Recursion又称递回是指一个函数直接或间接地实现自调用。在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法。绝大多数编程语言支持函数的自调用在这些语言中函数可以通过调用自身来进行递归。计算理论可以证明递归的作用可以完全取代循环。 计算机科学家尼克劳斯·维尔特如此描述递归 “ 递归的强大之处在于它允许用户用有限的语句描述无限的对象。因此在计算机科学中递归可以被用来描述无限步的运算尽管描述运算的程序是有限的。” ——尼克劳斯·维尔特 2.条件 ①递归必须设置一个明确的终止条件当满足该条件时递归停止不满足该条件时继续递归。PS : 如果一个递归没有设置终止条件那么它会无限制地递归下去形成死递归类似于死循环称为“死龟了”。 ②一个使用了递归的函数其处理的数据规模一定是在递减的。即一个有效的递归它的递归总次数是一定的执行的次数越多剩余的规模就越小。 3.比较 这里的“比较”指的是递归和循环的比较。 理论上讲可以用循环解决的问题都可以转化为用递归解决但是用递归解决的的问题有时候并不能用循环解决。 递归结构简洁更易理解但是递归所需存储空间大运行速度慢 循环结构复杂不易理解但是循环所需存储空间小运行速度快。 二、 如何理解递归 1.函数调用其他函数示例 : 递归本质上利用的栈的原理满足“先进后出”的特点。要想理解递归必须先理解函数中是如何调用其他函数的我们先来看下面一段代码 :
# include stdio.hvoid f1();
void f2();
void f3();int main(void)
{f1();return 0;
}void f1()
{f2();printf(AAAAA\n);return;
}void f2()
{f3();printf(BBBBB\n);return;
}void f3()
{printf(CCCCC\n);return;
} 你认为以上代码的输出结果是什么输出结果如下 : 解释 : main函数先进栈main函数中调用了f1函数因此f1函数会进栈因为f1函数中又调用了f2函数因此f2函数接着进栈又因为f2函数中又调用了f3函数所以f3函数跟着进栈。 根据栈“先进后出”的特点f3函数最后进栈就要最先出栈而f3中的代码执行完毕后打印出CCCCC继而返回f2中f2函数执行完毕后打印出BBBBB接着f2出栈返回f1中f1再打印出AAAAA最后f1出栈所以出栈的顺序是f3 —— f2 —— f1。 那么递归其实就是把“函数中调用其他函数”给变成了“函数中调用函数自己本身”同样是栈的原理同样满足“先进后出”的特点。 2.函数调用函数自身示例 : 我们再来看一段简单的递归求某个数阶乘的代码如下 :
# include stdio.hint factorial(int);int main(void)
{int factorial_value factorial(4);printf(4的阶乘 %d, factorial_value);return 0;
}int factorial(int n)
{if (n 1 || n 0)return 1;return n * factorial(n - 1);
} 运行结果 : 解释 : 首先我们可以看到这段代码的目的就是求4的阶乘。main函数先进栈main函数中调用了factorial方法factorial [fækˈtɔriəl] 就是“阶乘”的意思factorial方法要进栈此时我们传入的实参 4接着因为4不满足factorial方法中if语句的判断条件因此要执行return语句而return语句的内容n * factorial(n - 1)中又调用了factorial函数自身只不过这次调用的效果是factorial(3)了所以factorial(3)方法中包含的局部变量要进栈同理factorial(2)方法包含的局部变量进栈factorial(2)方法中有调用factorial(1)方法所以factorial(1)方法包含的局部变量最后进栈。所以整个求4的阶乘的递归过程中factorial函数的压栈顺序为factorial(4) —— factorial(3) —— factorial(2) —— factorial(1) 在factorial(1)方法中满足if条件语句因此factorial(1)方法要返回1接着factorial(1)方法执行完毕factorial(1)方法出栈回到factorial(2)方法factorial(2)方法返回 2 * factorial(1) 2 * (1)接着factorial(2)方法出栈回到factorial(3)方法factorial(3)方法返回3 * (2 * 1)接着factorial(3)方法出栈回到factorial(4)方法factorial(4)方法返回4 * (3 * 2 * 1)。所以整个求4的阶乘的递归过程中factorial函数的出栈顺序为factorial(1) —— factorial(2) —— factorial(3) —— factorial(4)。直到递归到factorial(1)时停止递归开始逐层返回。 我们可以对以上代码进行优化使得我们可以求任意一个数的阶乘代码如下 :
# include stdio.hint factorial(int);int main(void)
{printf(请输入你想求阶乘的数提示 : 大于等于0的整型数据);int i;scanf(%d, i);int factorial_value factorial(i);if (factorial_value -1)printf(请传入大于等于0的数);elseprintf(\n所求数%d的阶乘 %d\n, i, factorial_value);return 0;
}int factorial(int n)
{if (n 0){return -1;}else if (n 0 || n 1)return 1;return n * factorial(n - 1);
} 运行效果 : (如下GIF图) 3.函数调用自身的底层操作 : ①在主调函数调用被调函数之前—— 1° 系统要将传入的实参和主调函数的地址等信息传递给被调函数保存。传递主调函数的地址其目的是为了确保程序执行的连续性即当被调函数执行完毕准备出栈时可以根据这个地址来找到接下来需要执行的语句。 2° 系统要为被调函数的局部变量包括形参和方法体定义的变量分配内存空间。 3° 将控制权限由主调函数转移到被调函数的入口准备执行被调函数。 ②在被调函数返回主调函数之前—— 1° 系统要保存被调函数的返回结果即对它做一个备份用于返回给主调函数。 2° 系统要释放掉为被调函数分配的内存空间。不包括动态内存 3° 按照被调函数保存的返回地址将控制权限由被调函数转移到主调函数。 ③在出现多个函数相互调用的情况时—— 1° 按照“后调用先返回”的原则所涉及到的信息传递和控制转移等操作需要借助“栈”来实现。 2° 系统会将整个程序运行所需的内存空间安排在一个栈中每当调用一个函数时就在栈顶分配一块空间用于压栈每当退出一个函数时就释放这块区域完成出栈操作当前运行的函数永远位于栈顶的位置。 三、递归的具体实例 1.求1~100的和 : 思路 : 类似于上文中求阶乘的步骤我们可以先进行一个if条件语句的判断——n是否等于1该判断可作为递归结束的条件当n不满足等于1的条件时就return n f(n - 1)f代表当前求和的函数。 代码 :
# include stdio.hint sum(int);int main(void)
{printf(\n1~100的和 );int sum_value sum(100);printf(%d\n, sum_value);return 0;
}int sum(int n)
{if (n 1)return 1;return n sum(n - 1);
} 运行结果 : 优化 : 我们可以令用户自定义传入sum函数的实参达到求1~n的和的目的。代码如下 :
# include stdio.hint sum(int);int main(void)
{printf(请输入你想求的1到某个数的和);int n;scanf(%d, n);int sum_value sum(n);if (sum_value ! -1){printf(\n1~%d的和 , n);printf(%d\n, sum_value);}else printf(请输入合法的数字);return 0;
}int sum(int n)
{if (n 1)return -1;else if (n 1)return 1;return n sum(n - 1);
} 运行效果如下GIF图 2. 汉诺塔问题 : 背景 : 传说越南河内某间寺院有三根银棒上串 64 个金盘。寺院里的僧侣依照一个古老的预言以特定规则移动这些盘子预言说当这些盘子移动完毕世界就会灭亡。移动金盘的规则如下—— ①每次只能移动一个圆盘 ②大盘不能叠在小盘上面。 ③设三根银棒分别为ABC最终要将A棒上的64个金盘移动到C棒上移动过程中可借助B棒来临时存放金盘。 思路 : 仍是递归的思想—— ①我们先从最简单的1个金盘说起若想将一个金盘从A棒移动到C棒直接移动就可以不需要借助B棒。 ②当A棒有2个金盘时我们可以先将上面的第一个金盘放到B棒上再把A棒的第二个金盘放到C棒最后将B棒的第一个金盘放到C棒。(该目标的实现借助了B棒B棒上临时存放了第1个金盘 ③当A棒有3个金盘时我们可以设法将A棒上面的2个金盘放到B棒上将第三个金盘从A棒移动到C棒再设法将B棒临时存放的两个金盘放到C棒上。其中“设法将A棒上面的2个金盘放到B棒上” 和 “设法将B棒上面的两个金盘放到C棒上” 这两个步骤其实就是在重复②的步骤。 ④通过③我们可知金盘的数量每增加1个其实都是在重复之前金盘数量时的步骤最核心的步骤就是将A棒最下面的那个最大的金盘从A棒放到C棒。而要想实现最核心的步骤必须分三步走1° 先设法将A棒上面的n-1个金盘借助C棒移动到B棒使A棒只剩下最下面的最大的金盘同时C棒为空这样才能2° 接着把最大的金盘从A移动到C之后再3° 设法将B棒上面的n - 1个金盘借助A棒移动到C棒。 代码 :
# include stdio.hint count 0;
void hanoi(int, char, char, char);int main(void)
{printf(请输入汉诺塔的层数, floors );int floors;scanf(%d, floors);hanoi(floors, A,B,C);if (count 0)printf(总共需要执行的步骤有%d步\n, count);return 0;
}void hanoi(int n, char a, char b, char c)
{if (n 1){printf(请传入合法有效的数据);return;}else if (n 1){printf(%c -- %c\n, a,c);count;return;}hanoi(n - 1, a,c,b);printf(%c -- %c\n, a,c);count;hanoi(n - 1, b,a,c);return;
}/*注意 : ①hanoi(n - 1, a,c,b) 和 hanoi(n - 1, b,a,c)这两个步骤是相互联系的。②else if语句中的printf语句其目的是为了帮助完成hanoin - 1, a,c,b)操作最后的printf语句其目的是完成最核心步骤————将最大的盘从A棒移动到C棒。
*/ 运行效果 : (如下GIF图 3.斐波那契数 : 介绍 : Fibonacci[/ˌfɪbəˈnɑːtʃi/]斐波那契数意大利语Successione di Fibonacci又译为菲波拿契数、菲波那西数、斐氏数、黄金分割数。所形成的数列称为斐波那契数列又译为菲波拿契数列、菲波那西数列、斐氏数列、黄金分割数列。这个数列是由意大利数学家斐波那契在他的《算盘书》中提出。 在数学上斐波那契数是以递归的方法来定义 令F0 0; F1 1; 则Fn F(n - 1) F(n - 2)其中n ≥2。即——从数列的第三项开始每一项的值等于前面两项之和称为斐波那契数列。斐波那契数列的前几项如下所示 : PS : 0不是第一项而是第零项斐波那契数列在文本上从1开始。 思路 : 设n代表斐波那契数列的第n项当n等于1或者等于2时可以直接返回1当n大于2时要想求出斐波纳契数列的第n项必须知道它前面的两项分别是多少而要想知道它前面的两项分别是多少就又得知道这两项再分别往前的两项是多少依次递归下去直到n 1或者n 2的情况时return 1接着再逐层返回回到你想求出的第n项。 代码 :
/*斐波那契数列2023.4.1
*/# include stdio.hint fibonacci(int);int main(void)
{printf(请输入你想输出斐波那契数列的前几项\nnum );int num;scanf(%d, num);if (fibonacci(num) -1){printf(请输入合法数据!);}else {int i;for (i 1; i num; i){printf(%d\t, fibonacci(i));}}return 0;
}int fibonacci(int n)
{if (n 1)return -1;else if (n 1 || n 2)return 1;return fibonacci(n - 1) fibonacci(n - 2);
} 运行效果如下GIF图所示
