东莞++网站建设,白山网站建设公司,新闻发布会邀请哪些媒体,陕西城乡建设局网站函数递归 前言1.递归案例:案例一#xff1a;取球问题案例二#xff1a;求斐波那契额数列案例三#xff1a;函数实现n的k次方案例四#xff1a;输入一个非负整数#xff0c;返回组成它的数字之和案例五#xff1a;元素逆置案例六#xff1a;实现strlen案例七#xff1a;… 函数递归 前言1.递归案例:案例一取球问题案例二求斐波那契额数列案例三函数实现n的k次方案例四输入一个非负整数返回组成它的数字之和案例五元素逆置案例六实现strlen案例七爬楼梯1.0案例八爬楼梯2.0案例九求阶乘案例十求阶乘和案例十一杨辉三角案例十二最大公约数案例十四汉偌塔 2.递归与迭代3.何时使用递归 前言 程序调用自身的编程技巧称为递归 recursion。 递归做为一种算法在程序设计语言中广泛应用。 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。 递归策略 只需少量的程序就可描述出解题过程所需要的多次重复计算大大地减少了程序的代码量。 递归的主要思考方式在于把大事化小 递归的两个必要条件
存在限制条件当满足这个限制条件的时候递归便不再继续。每次递归调用之后越来越接近这个限制条件
1.递归案例:
案例一取球问题 在 n 个球中任意取 m 个不放回求有多少种不同取法。 分析 假设有一个特殊球此球的状态只有两种被取到和没有被取到。 若被取到那么只需在n-1个球中取m-1个球。 若没有被取到需在n-1个球中取m个球。 代码演示
int ball(int n, int m)
{if (m n)return 0;if (n m)return 1;if (m 0)return 1;return ball(n - 1, m - 1) ball(n - 1, m);
}
int main()
{int n 0;int m 0;scanf(%d%d, n, m);printf(%d\n, ball(n, m));return 0;
}运行结果 案例二求斐波那契额数列 这个数列从第3项开始每一项都等于前两项之和。 分析: 在数学上斐波那契数列以如下被以递推的方法定义 代码演示
int Fib(int n)
{if (n 2)return 1;elsereturn Fib(n - 1) Fib(n - 2);
}
int main()
{int n 0;scanf(%d, n);//20int ret Fib(n);printf(%d\n, ret);return 0;
}运行结果 案例三函数实现n的k次方
分析 指数为负数用double%lf打印 代码演示
double Pow(n, k)
{if (k 0){return n * Pow(n, k-1);}else if(k 0){return 1;}else{return 1.0 / Pow(n, -k);//实现指数为负数}}
int main()
{int n 0;int k 0;scanf(%d %d, n, k);double ret Pow(n, k);printf(%lf\n, ret);//double打印用lfreturn 0;
}运行结果 案例四输入一个非负整数返回组成它的数字之和
分析 当一个数是大于0 的数时要得结果等于这个数模%10得到最低位的数字然后再加它的次低位…一直加到最高位的数字这些数字用给这个数除以10得到递归调用这个函数即可。 代码演示
int DigitSum(int n)
{if (n 9){return n;}else{return DigitSum(n / 10) n % 10;}
}
int main()
{int n 0;scanf(%d, n);int ret DigitSum(n);printf(%d\n, ret);return 0;
}运行结果 案例五元素逆置
分析 代码演示
#includestring.h
void reverse_string(char* str)
{size_t len strlen(str);char temp str[0];str[0] str[len - 1];str[len - 1] \0;if (strlen(str1) 2){reverse_string(str1);}str[len - 1] temp;
}
int main()
{char arr[] abcdef;reverse_string(arr);printf(%s\n, arr);//字符串用%s打印return 0;
}运行结果 案例六实现strlen
分析 代码演示
size_t my_strlen(char* str)
{if (*str \0)//(str0)return 0;elsereturn 1 my_strlen(str 1);
}
int main()
{char arr[] abcdef;size_t len my_strlen(arr);printf(%zd, len);return 0;
}运行结果 案例七爬楼梯1.0 树老师爬楼梯他可以每次走 1 级或者 2 级输入楼梯的级数求不同的走法数。 分析 如果从第0级台阶爬到第1级台阶有1种方法爬1个台阶 如果从第0级台阶爬到第2级台阶有2种方法爬1个台阶 或 爬2个台阶 如果从第0级台阶爬到第3级台阶有3种方法 先从第0级台阶爬到第1级台阶再从第1级台阶爬到2级台阶再从第2级台阶爬到第3级台阶即1,1,1 先从第0级爬1个台阶到第1级台阶再从第1级爬2个台阶到第3级即1,2 先从第0级爬2个台阶到第2级台阶再从第2级爬1个台阶到第3级即2,1 如果从第0台阶爬到第4级台阶有5种方法 1,1,1,1 1,1,2 1,2,1 2,1,1 2,2 归纳发现原理同斐波那契数列 代码演示
int stair(int n)
{if (n 1)return 1;if (n 2)return 2;return stair(n - 1) stair(n - 2);
}
int main()
{int n 0;scanf(%d, n);printf(%d\n, stair(n));return 0;
}运行结果 案例八爬楼梯2.0 树老师爬楼梯他可以每次走 1 级、2 级或者 3 级输入楼梯的级数求不同的走法数。 原理同上
代码演示
int stair(int n)
{if (n 1)return 1;if (n 2)return 2;if (n 3)return 4;return stair(n - 1) stair(n - 2) stair(n - 3);
}
int main()
{int n 0;scanf(%d, n);printf(%d\n, stair(n));
}运行结果 案例九求阶乘
代码演示
int Fac(int n)
{if (n 1)return 1;elsereturn n* Fac(n - 1);
}
int main()
{int n 0;scanf(%d, n);int r Fac(n);printf(%d\n, r);return 0;
}运行结果 案例十求阶乘和 求 1!2!3!4!5!6!7!…n!的和。 代码演示
int factorial(int n)
{if (n 1)return 1;return n * factorial(n - 1);
}
int main()
{int n 0;int sum 0;int i 0;scanf(%d, n);for (i 1; i n; i){sum factorial(i);}printf(%d\n, sum);return 0;
}运行结果 案例十一杨辉三角 输入要打印的层数打印杨辉三角 分析 根据观察第一列和对角线上的元素之外其余元素的值均为前一行上的同列元素和前一列元素之和。我们可以依靠递归相加就行实现 #include stdio.h
long Tri(int r, int c)
{return (c 1 || c r) ? 1 : Tri(r - 1, c - 1) Tri(r - 1, c);
}
int main()
{int i 0;int j 0;int n 0;scanf(%d, n);for (i 1; i n; i) // 输出n行{for (j 0; j n - i; j) //每行前面补空格显示成等腰三角形 printf( );for (j 1; j i; j)printf(%6d, Tri(i, j)); //计算并输出杨辉三角形 printf(\n);}return 0;
}运行结果
案例十二最大公约数
//代码演示
int gcd(int a, int b)
{int t 0;if (a b){t a;a b;b t;}if (b 0)return a;return gcd(b, a % b);
}
int main()
{int a 0;int b 0;scanf(%d%d, a, b);printf(%d\n, gcd(a, b));return 0;
}运行结果:
案例十四汉偌塔 汉诺塔问题就是将A柱上n个圆全部移动到C上过程中可以借助B柱但要始终保持小圆在大圆上面 对于n阶汉诺塔的移动次数 #define _CRT_SECURE_NO_WARNINGS
#includestdio.h
#includemath.h
int main()
{int num 0;scanf(%d, num);//塔数printf(完成%d层的汉诺塔需要%d步\n, num, (int)pow(2,num) - 1);return 0;
}运行结果 分析 步骤1所含步数就是n-1个圆盘移动所需的次数我们可以将其步数看做f(n-1)。 步骤2所含步数为1。 步骤3所含步数与步骤1相似我们也将其步数看做f(n-1)。 再观察表格中汉诺塔的移动次数对于一阶汉诺塔移动次数就为1对于其他的阶数则为前一阶汉诺塔移动次数 1 前一阶汉诺塔移动次数。 不难得出递推表达式f(n-1) 1 f(n-1) 2 * f(n - 1) 1
#define _CRT_SECURE_NO_WARNINGS
#includestdio.h
int Hanio_twice(int num)
{if(1 num)return 1;elsereturn 2 * Hanio_twice(num - 1) 1;
}
int main()
{int num 0; scanf(%d, num);//塔数int ret Hanio_twice(num);printf(完成%d层的汉诺塔需要%d步\n, num, ret);return 0;}运行结果 分析 我们观察移动步骤发现只有一个圆盘时移动步骤为A-C两个圆盘时为A-BA-CB-C。 那么对于n阶汉诺塔呢我们对其进行推演 1.把n-1个圆盘从A移动到B 2.把第n个圆盘从A移动到C 3.把n-1个圆盘从B移动到C 那n-1个圆盘如何从A移动到B呢 1.把n-2个圆盘从A移动到C 2.把第n-1个圆盘从A移动到B 3.把n-2个圆盘从C移动到B 同样的对于把n-1个圆盘从B移动到C也可以推测出来 1.把n-2个圆盘从B移动到A 2.把第n-1个圆盘从B移动到C 3.把n-2个圆盘从A移动到C 通过这些推演我们发现汉诺塔的移动可以通过递归展开那么以上推演步骤我们可以将其作为递归的步骤。 思路定义A,B,C三个字符表示A,B,C三柱定义n为阶数那么n-1也就是移动步骤中需要移动的圆盘数。 对于一阶汉诺塔直接移动即可对于其他的阶数则需要通过递归展开为n阶汉诺塔的移动步骤。
//代码演示
void move(char pos1, char pos2)
{printf( %c - %c \n, pos1, pos2);
}
//pos1起始位置
//pos2中转位置
//pos3目标位置
void Hannoi(int n, char pos1, char pos2, char pos3)
{if (n 1){move(pos1, pos3);}else{Hannoi(n - 1, pos1, pos3, pos2);move(pos1, pos3);Hannoi(n - 1, pos2, pos1, pos3);}
}
int main()
{/*Hannoi(1, A, B, C);*///Hannoi(2, A, B, C);Hannoi(3, A, B, C);return 0;
}运行结果 2.递归与迭代
听过上面函数递归案例发现有问题如下 在使用 Fib 这个函数的时候如果我们要计算第50个斐波那契数字的时候特别耗费时间。 使用 Fac 函数求10000的阶乘不考虑结果的正确性程序会崩溃。 为什么呢 我们发现 Fib 函数在调用的过程中很多计算其实在一直重复。 那我们如何改进呢 在调试 Fac 函数的时候如果你的参数比较大那就会报错 **stack overflow栈溢出**这样的信息。 系统分配给程序的栈空间是有限的但是如果出现了死循环或者死递归这样有可能导致一直开辟栈空间最终产生栈空间耗尽的情况这样的现象我们称为栈溢出。 那如何解决上述的问题 将递归改写成非递归。 使用static对象替代 nonstatic 局部对象。在递归函数设计中可以使用 static 对象替代nonstatic 局部对象即栈对象这不仅可以减少每次递归调用和返回时产生和释放 nonstatic 对象的开销而且 static 对象还可以保存递归调用的中间状态并且可为各个调用层所访问。 比如下面代码就采用了非递归的方式来实现 n的阶乘 int Fac(int n)
{int i 0;int r 1;for (i 1; i n; i){r r * i;}return r;
}
int main()
{int n 0;scanf(%d, n);int r Fac(n);printf(%d\n, r);return 0;
}求第n个斐波那契数 int Fib(int n)
{int a 1;int b 1;int c 1;while (n 3){c a b;a b;b c;n--;}return c;
}
int main()
{int n 0;scanf(%d, n);//20int ret Fib(n);printf(%d\n, ret);return 0;3.何时使用递归 如果使用递归很容易想到,写出的代码没有明显的缺陷,那我们就可以使用递归 但如果写出的递归代码,有明显问题,比如:栈溢出,效率低下等,那我们还是使用迭代的方式来解决. 本次专题已结束不久将来会有更多专题与大家见面
