『递归』递归概念与典型实例
活动地址:CSDN21天学习挑战赛
👨🎓作者简介:一位喜欢写作,计科专业大二菜鸟
🏡个人主页:starry陆离
🕒首发日期:2022年8月2日星期二
🌌上期文章:『算法导论』什么是算法?什么是程序?
📚订阅专栏:『算法分析与设计』
🍁每日推荐:『牛客网-面试神器』
如果文章有帮到你的话记得点赞👍+收藏💗支持一下哦
这里写目录标题
- 1.引言
- 2.递归的定义
- 3.递归的要素
- 4.递归特点
- 5.递归的特点
- 6.递归的优缺点
- 7.典型递归实例
-
- 7.1求阶乘
- 7.2Fibonacci数列
- 7.3青蛙跳台阶
@[TOC](『递归概念与典型实例』)
1.引言
问题:1-100求和
方法1:使用循环求和 1+2+3+4+5+6+……+99+100
伪代码:for i=1 to 100 sum = sum + i
方法2:换个角度思考
sum(n)表示1…n的和 sum(100) = sum(99) + 100 = sum(98) + 99 + 100 = …… = sum(1) + 2 + 3 + 4 + …… + 99 + 100 = 1 + 2 + 3 + 4 +…… + 99 + 100
2.递归的定义
在调用一个函数的过程中又出现直接或间接调用该函数本身,称为函数的递 归(Recursion)调用,这种函数称为递归函数
-
若p函数定义中调用p函数,称之为直接递归
-
若p函数定义中调用q函数,而q函数定义中又调用p函数,称之为间接递归
3.递归的要素
1、递归表达式 (递归方程)
2、递归结束条件 (边界条件)
int sum(int n){if(n==1)return 1;//递归结束条件else sum(n-1)+n;//递归表达式}
4.递归特点
(1) 需要解决的问题可以转化为一个或多个子问题来求解,而这些子问题的 求解方法与原问题完全相同,只是在数量规模上不同
(2) 递归调用的次数必须是有限的
(3) 必须有结束递归的条件来终止递归
5.递归的特点
(1) 定义是递归的(阶乘、斐波那契数列等)
(2) 数据结构是递归的(单链表、二叉树等)
(3) 问题的求解方法是递归的(汉诺塔、回溯法等)
6.递归的优缺点
递归的优缺点
优点:结构清晰,可读性强,而且容易用数学归纳法来证明算法的正确性, 因此它为设计算法、调试程序带来很大方便
缺点:递归算法的运行效率较低,无论是耗费的计算时间还是占用的存储空 间都比非递归算法要多
解决方法:在某些递归算法中可消除递归调用,使其转化为非递归算法
7.典型递归实例
7.1求阶乘
n!=1×2×3×……×n
int f(int n){if(n==1)return 1;//递归结束条件else n*f(n-1);//递归表达式}
7.2Fibonacci数列
斐波那契(Fibonacci)数列因数学家列奥纳多·斐波那 契以兔子繁殖为例引入,故又称为**“兔子数列”**。
int fibonacci(int n){if(n<=1)return 1;//递归结束条件 return fibonacci(n-1)+fibonacci(n-2);//递归表达式}
7.3青蛙跳台阶
一只青蛙一次可以跳上1级台阶,也可以跳上2级。
- 求该青蛙跳上一个n级的台阶总共有多少种跳法?
就是fibonacci
的变形题,读者可自行实现
🍁每日推荐:基础算法无论在研究生面试还是求职面试都是十分重要的一环,这里推荐一款算法面试神器:牛客网-面试神器;算法题只有多刷勤刷才能保持思路与手感,大家赶紧行动起来吧(温馨提示:常见的面试问答题库也很nice哦)
如果文章有帮到你的话记得点赞👍+收藏💗支持一下哦