- VisualStudio2022插件的安装及使用-编程手把手系列文章
- pprof-在现网场景怎么用
- C#实现的下拉多选框,下拉多选树,多级节点
- 【学习笔记】基础数据结构:猫树
递归和for循环(迭代法)很像,都是通过循环去完成一件事.
但采用Top-Down思维去设计的递归结构,又会比for多一些不同的能力。多什么能力?
先复习一下递归,递归的定义:递归(英语:Recursion),又译为递回,在数学与计算机科学中,是指在函数的定义中使用函数自身的方法.
递归的本质就在:递去,归来 两个流程中。 初学者刚接触会有点抽象,下面通过一些案例来认识.
假设需要你实现一个阶乘的计算函数, 阶乘的定义: 5的阶乘是 5*4*3*2*1=120 。
def factorial(number):
if number == 1:
return 1
else:
return number * factorial(number - 1)
print(factorial(5))
// 120
递归需要考虑三个条件:
递归的底层实现不是本文的重点,了解一下就行.
递归在编程语言的底层实现通常依赖于调用栈(call stack):
调用栈:
基线条件:
内存管理:
总结:
递归实现的效率和安全性与具体语言的特性和编译器的优化密切相关.
递归的底层实现,就是把相关变量数据(缓存)处理后,一层一层的压入栈,等到了基准条件后,在逐层拿出处理.
计算机眼里的递归: 计算机使用栈来记录正在调用的函数,叫调用栈.
有个局部变量 number 记录当前值.
处理任意多层事情的场景,都可以考虑用递归.
当问题和子问题具有递推关系,比如杨辉三角、计算阶乘.
具有递归性质的数据结构,比如链表、树、图.
反向性问题,比如取反操作.
这个才是本文重点要学习的.
当面对未来未知的情况时,考虑使用使用自上而下解决问题的思维.
两种编写计算函数的方法
两者区别? 在计算函数时,自下而上和自上而下是两种不同的思维方式和实现策略:
在计算函数时,特别是像阶乘这样的递归函数,可以使用两种主要的实现方式来实现递归计算:自下而上(bottom-up)和自上而下(top-down)。这些方法各有优缺点,理解它们有助于选择适合的实现方式来解决特定的问题。以下是对这两种实现方式的解释:
自下而上方法,也称为 迭代方法 或 动态规划方法,是指从最小的子问题开始逐步构建解决方案,直到解决原始问题。这种方法通常用于动态规划算法中,但也可以用于一些简单的递归问题.
实现思路:
0!
或 1!
开始。还是以计算阶乘的案例去介绍,自下而上实现方式:
def factorial_bottom_up(n):
if n < 0:
raise ValueError("Factorial is not defined for negative numbers")
result = 1
for i in range(2, n + 1):
result *= i
return result
# 示例用法
print(factorial_bottom_up(5)) # 输出 120
解释:
n!
。自上而下方法也称为 递归方法,是指从解决问题的最上层开始,递归地解决较小的子问题。这种方法在处理递归问题时非常自然(但可能存在重复计算的子问题,有些可以优化).
实现思路:
还是以计算阶乘的案例,展示自上而下实现:
def factorial_top_down(n):
if n < 0:
raise ValueError("Factorial is not defined for negative numbers")
if n == 0 or n == 1:
return 1
return n * factorial_top_down(n - 1)
# 示例用法
print(factorial_top_down(5)) # 输出 120
解释:
n
开始,递归调用 factorial_top_down(n - 1)
,直到达到基本情况。1
,逐层返回乘积结果。总结 。
自下而上:通常是迭代的方法,逐步构建解决方案,适用于动态规划和需要避免重复计算的情况。它通常较为高效,尤其是在解决子问题重复计算时.
自上而下:通常是递归的方法,直观地解决问题,但可能会有较高的时间复杂度和空间复杂度,尤其在处理大规模问题时。(可以通过记忆化(Memoization)来优化性能) 。
一般来说,自下而上的实现过程比较好理解,所以这里多列举一些自上而下的案例帮助思考, 。
自上而下的编程思考过程:
求和案例 假设我们要写一个 sum 函数,计算数组中所有数的和。如果给函数传入数组[1,2,3,4,5],那么它会返回这些数的和15.
我们需要做的第一件事就是想象已经有人实现了 sum 函数。(当然,你可能会有点难以接受,毕竟写函数是我们自己,怎么能假设别人写好了呢! 但可以试着忘掉这一点,先假装 sum 函数已经实现好了。) 。
接下来,来辨别子问题。比起科学,这个过程更像是艺术,只要你多练习就能进步。 在这个例子中,可以认为子问题是数组[2,3,4,5],即原数组中除第一个数以外的元素.
最后,来看看在子问题上调用 sum 函数会发生什么 ? 如果 sum 函数“已被正确实现”并且子问题是 [2,3,4,5],那么调用 sum([2,3,4,5])时会发生什么呢?会得到2+3+4+5的和,也就是14.
而要求[1,2,3,4,5]的和,只需向 sum([2,3,4,5])的结果再加上1即可.
请使用编程语言实现一下:
mylist = [1, 2, 3, 4, 5]
def mysum(alist):
if len(alist) == 1:
return alist[0]
else:
# alist[-1] = alist[len(alist)-1]
alist[0] += alist[-1]
return mysum(alist[0:len(alist) - 1])
print(mysum(mylist))
# 15
为什么需要用递归?
请写出代码:
todo
这个是一个很实用的案例,之前想将多个pyload 以不同位置组合成一个整体,就遇到这个难题.
请写出代码:
todo
最后此篇关于以Top-Down思维去解决问题——递归的文章就讲到这里了,如果你想了解更多关于以Top-Down思维去解决问题——递归的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。
一、前言: Python如何使用OS模块调用cmd 在os模块中提供了两种调用 cmd 的方法,os.popen() 和 os.system() os.system(cmd) 是在执行command命
我对双链表进行了简化。我的双链表是一个以头和尾为节点的结构。 有一个函数可以创建列表并返回它。在同一函数中,我执行尾节点和头节点之间的链接。问题是,当我返回列表(因此转到函数之外)时,所有链接都消失了
我有这个信息。 let params2: [String: AnyObject] = [ "app_token": myapptoken, "member_access_token":
关闭。这个问题是opinion-based .它目前不接受答案。 想要改进这个问题? 更新问题,以便 editing this post 可以用事实和引用来回答它. 关闭 7 年前。 Improve
我正在尝试发出解析为特定 IP 的 cURL 请求。从我读过的所有内容来看,这在我看来在语法上是正确的,但我仍然看到“无法解决主机错误”。有人能指出我正确的方向吗?我看到了各种错误: curl —-r
我正在尝试使用 curl 在 jira 服务器中获取数据。我试过这个命令 curl -u username:password -X GET -H "Content-Type: applicat
因此,下面的代码有时会起作用,有时它会添加&符号(到复制缓冲区),我试图从文本字符串中删除它。 代码的要点是将字符串从正确位置复制到与号之前。但是,在随机情况下,它仍然会添加 & 符号。 Privat
p = Int('p') q = Int('q') s = Solver() s.add(1<=p<=9, 1<=q<=19, 5<(3*p-4*q)<10) s.check() print s.mo
我在这里阅读了分配问题的解决方案:http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=hungarianAlgorithm 我了解 O(n
控制台中显示警告: the id param was not provided. 文档提到将使用当前路由: current is the current Route by default (most
我正在尝试使用hector-core作为grails Maven构建中的依赖项。 me.prettyprint hector-core 1.0-3 bundle 我收到一个错误 [
我正在尝试使用 JavaScript 变得更好,并且我在破坏页面方面做得非常好:))))) 我正在尝试使用 Firebug 进行调试,但一开始有点困惑。它的哪个选项卡用于调试 JavaScript?我
我正在使用最新的 Angular + Firebase 并尝试设置登录授权系统。我有包含登录+注册链接的 home.html,转到 login.html 并添加凭据工作正常(提交时记录正确的 UID)
我有一个 iPad 应用,现在需要将其转换为通用应用。我已将目标设置为 Universal,现在它也可以部署到 iPhone,但是,我有一个主要问题:即使我已经创建了我的 main分别查看两种设备类型
我在 CSS 中使用媒体查询来根据 IE11 和 Chrome 的屏幕分辨率缩放我的网页。当我运行 this webpage在我的 2 个不同屏幕上的 chrome(顺便说一句,我用它来确定我的最小宽
我正在解决nodeschool练习“Juggling Async”,我是这样解决的 var http=require("http"); var urls=process.argv.slice(2,pr
我试图相对神秘地要求一个文件,发生了以下情况 这很好,它指向 /Users/marcos/Desktop/Taper/lib/utils.js myPath = "/Users/marcos/Desk
我正在尝试解决一个项目,但遇到了问题。 • 您的程序应该显示一个菜单,允许用户执行以下操作以下操作(注:使用GUI): 添加新客户 删除客户 修改客户信息//此选项必须显示子菜单: --------1
我需要 x 图标来删除输入字段值1. 当用户键入任何内容时,将显示“x”图标 如果输入框中没有可用的值,x 将被隐藏 当输入框中的值可用并且焦点移出输入框时,我们需要隐藏 x 图标并聚焦,我们需要再次
我正在使用 ajs(1.4.7) 和 angular-ui-router(0.2.15) 开发一个简单的 AJS 应用程序。 经历了this文章并选择了路由解析技术。 这是我遇到的错误 错误:[$in
我是一名优秀的程序员,十分优秀!