《算法图解》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 条评论
登录 后参与评论

相关文章

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

入住腾讯云+社区

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

561
来自专栏软件开发 -- 分享 互助 成长

C++类的复制构造函数和赋值运算符

前言: C++面向对象的编程过程中,凡是在类中运用到动态内存分配的时候总是会写一个显示的复制构造函数和赋值重载运算符,本文将结合C++ Primer Plus一...

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

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

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

2847
来自专栏androidBlog

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

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

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

生成器&迭代器

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

33710
来自专栏Python小屋

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

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

2666
来自专栏XAI

腾讯AI-JavaAPI示例代码

https://gitee.com/xshuai/ai/tree/master/AIDemo/src/main/java/com/xs/tencent

2718
来自专栏专注研发

delete与delete[]的区别

一直对C++中的delete和delete[]的区别不甚了解,今天遇到了,上网查了一下,得出了结论。做个备份,以免丢失。

711
来自专栏Python小屋

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

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

4218
来自专栏书山有路勤为径

栈与队列基础知识

栈,是先进后出的线性表,标准STL的栈包括如下5种操作,设栈S: 1.取出栈顶元素:S.top(); 2.判断栈是否为空:S.empty(); 3.将元素...

702

扫码关注云+社区