《算法图解》NOTE 3 递归1.定义2递归结构2.适用场合3.应用案例

这是《算法图解》的第二篇读书笔记,内容主要涉及递归。

1.定义

递归是一种解决问题的方式。其基本思路是将问题分解为与原问题的解决原理相同但规模更小的子问题后,解决并获得子问题的答案,之后逐步将子问题的答案合并,以获取原文提的答案。

2递归结构

递归在编程中展示的明显特为函数在运行过程中调用函数自身。 形如下方的示例

def recursion_fun(i=0):
    #基递归停止条件 base case
    if i==100:
        return None
    #递归条件 recursive case
    i=I+1
    print ('running the function the' + str (i)+'tiem')
    recursion_fun(i)

上述在运行过程中函数会调用本身,但为避免造成死循环,递归函数会有一个基线条件(base case)用于判断函数何时终止递归。 因此,递归函数的结构分为两部分,基线条件:用于终止递归;递归条件:递归函数用于递归的代码。

2.适用场合

递归主要适用于将问题分解为子问题后,子问题的解法与原问题相同的场合。如简单的阶乘、斐波拉切数列的求和、深度优先搜索和广度优先搜索等。 递归算法能够很好地展示解决问题的思路,但其缺点也很明显,内存的使用率高。因为递归算法运行时,递归函数会不断调用本身。此时,外层的递归函数仍在运行,会占用内存。因此,递归函数的调用次数越多,占用的内存就越大。 综上所述,若对算法的性能要求较高,可考虑使用循环替代递归的思路来解决问题。 例如,有向图的深度优先搜索递归算法,可使用栈结构添加未访问的访问节点,并使用循环来访问由栈结构获取的节点。

3.应用案例

#阶乘,n!为阶乘数
def factor(n,i=0):
    if n<0:
        return None
    if i>n or n=0 or i=1:
        return 1
    i=I+1
    return i*factor(n,i)

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏http://www.cnblogs.com

生成器&迭代器

一.生成器 在介绍生成器表达式之前,先看下列表表达式: 1 >>> l = [i for i in range(50) if i % 2] #生成...

34610
来自专栏数据小魔方

左手用R右手Python系列之——数据框与apply向量运算

R语言与Python中的apply函数都有着丰富的应用场景,恰到好处的使用apply函数,可以避免在很多场景下书写冗余的代码,这不仅能提高代码可读性,而且提高代...

76611
来自专栏Python小屋

Python 3.6.x字符串格式化方法小结

1 使用%符号进行格式 使用%符号进行字符串格式化的形式如下图所示,格式运算符%之前的部分为格式字符串,之后的部分为需要进行格式化的内容。 ? Python...

3056
来自专栏云霄雨霁

子字符串查找----KMP算法

1670
来自专栏数据结构与算法

P3374 【模板】树状数组 1 单点修改与区间查询

题目描述 如题,已知一个数列,你需要进行下面两种操作: 1.将某一个数加上x 2.求出某区间每一个数的和 输入输出格式 输入格式: 第一行包含两个整数N...

3007
来自专栏androidBlog

归并排序 递归版和非递归版的实现(java)

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/gdutxiaoxu/article/details/...

2891
来自专栏Python小屋

Python把列表中的数字尽量等分成n份

问题描述:假设一个列表中含有若干整数,现在要求将其分成n个子列表,并使得各个子列表中的整数之和尽可能接近。 下面的代码并没有使用算法,而是直接将原始列表分成n...

5388
来自专栏锦小年的博客

Python数据分析(3)-numpy中nd数组的创建

1、ndarray的内存结构 和其他的库一样,每个库都可能有自己独特的数据结构,例如OpenCV,numpy库的多维数组叫做ndarray( N dimensi...

2268
来自专栏AILearning

一个面试题:截取字符串的函数,输入为一个字符串和字节数,输出为按字节截取的字符串

一个面试题: 编写一个截取字符串的函数,输入为一个字符串和字节数,输出为按字节截取的字符串。 但 是要保证汉字不被截半个,如“我ABC”4,应该截为“我AB”,...

2489
来自专栏面朝大海春暖花开

入住腾讯云+社区

对于的github基础代码https://github.com/chywx/JavaSE

2361

扫码关注云+社区

领取腾讯云代金券