> 文档中心 > 『递归』递归概念与典型实例

『递归』递归概念与典型实例

活动地址: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哦)
『递归』递归概念与典型实例

如果文章有帮到你的话记得点赞👍+收藏💗支持一下哦