购物车网站设计,旅游网站模板,北京网站开发公司排名,爱站网站seo查询工具#x1f308;个人主页: Aileen_0v0 #x1f525;系列专栏:PYTHON数据结构与算法学习系列专栏#x1f4ab;没有罗马,那就自己创造罗马~
目录
递归的起源
什么是递归? 利用递归解决列表求和问题
递归三定律
递归应用-整数转换为任意进制数
递归可视化
画…
个人主页: Aileen_0v0 系列专栏:PYTHON数据结构与算法学习系列专栏没有罗马,那就自己创造罗马~
目录
递归的起源
什么是递归? 利用递归解决列表求和问题
递归三定律
递归应用-整数转换为任意进制数
递归可视化
画一个正方形
画一个五角星
画一个九边形
画圆形
画一个等腰三角形
利用递归画一个螺旋
利用递归画一颗分形树
利用递归画一个谢尔平斯基三角形 递归的起源
递归是一种算法它利用函数的自身调用来解决问题。递归的历史可以追溯到古代的数学家和逻辑学家如希腊哲学家亚里士多德和印度数学家阿耶尔巴塔。然而递归算法的实际应用可以追溯到早期的计算机科学尤其是在20世纪40年代和50年代的计算机发展初期。
在20世纪初数学家David Hilbert提出了“希尔伯特问题”其中包括一个著名的问题——哥德尔不完备定理。这个定理表明任何一个形式化的系统都无法证明自身完备。这导致了一些数学家开始研究递归函数因为递归函数是一种强大的工具可以用来刻画数学中的可计算性概念。在20世纪40年代递归理论被广泛研究它为计算机科学的发展奠定了基础。
早期计算机如ENIAC是通过执行单个指令来执行操作的因此递归算法在这些机器上的执行效率较低。然而随着计算机硬件和编程语言的发展递归算法变得更加普遍和有效。今天递归算法被广泛用于计算机科学中的许多应用领域如数据结构设计、图像处理、机器学习和自然语言处理。 什么是递归? 递归是一种解决问题的方法其精髓在于将问题分解为规模更小的相同问题持续分解直到问题规模小到可以用非常简单直接的方式来解决。递归的问题分解方式非常独特其算法方面的明显特征就是:在算法流程中调用自身。 递归为我们提供了一种对复杂问题的优雅解决方案精妙的递归算法常会出奇简单令人赞叹。 问题:
给定一个列表返回所有数的和列表中数的个数不定需要一个循环和一个累加变量来迭代求和
def Listsum(nl):sum 0for i in nl:sum ireturn sumprint(Listsum([1,2,3,4])) 利用递归解决列表求和问题
程序很简单但假如没有循环语句 ?既不能用for也不能用while还能对不确定长度的列表求和么? 递归三定律 1.结束条件 2.向基态前进 3.自己调用自己 递归应用-整数转换为任意进制数
我们用最熟悉的十进制分析下这个问题
十进制有十个不同符号: convString 0123456789比十小的整数转换成十进制直接查表就可以了: convString[n]
比十大的整数想办法把比十大的整数拆成一系列比十小的整数逐个查表比如七百六十九拆成七、六、九查表得到769就可以了
所以在递归三定律里我们找到了“基就是小于十的整数本结束条件”
拆解整数的过程就是向“基本结束条件”演进的过程 我们用整数除和求余数两个计算来将整数一步步拆开除以“进制基base(// base)对“进制基”求余数 (% base) #n为转换的数字 base为进制数
def tostring(n,base):coverstring 0123456789if n base :return coverstring[n]else:return tostring(n // base , base) coverstring[n % base]
print(tostring(1999,10)) 递归可视化 画一个正方形
import turtle
t turtle.Turtle()
#通过四次向右转90度画一个边长为100的正方形
for i in range(4):t.forward(100)t.right(90)
turtle.done() 画一个五角星
#画五角星
import turtle
t turtle.Turtle()
t.pencolor(red)
t.pensize(3)
for i in range(5):t.forward(100)t.right(144)
t.hideturtle()turtle.done() 画一个九边形
#画九边形
import turtle
t turtle.Turtle()
t.pencolor(blue)
t.pensize(10)
for i in range(9):t.forward(100)t.left(320)
t.hideturtle()
turtle.done() 画圆形
#画圆形
import turtle
t turtle.Turtle()
t.pencolor(blue)
t.pensize(10)
for i in range(1):t.circle(180)
t.hideturtle()
turtle.done() 画一个等腰三角形
#画等腰三角形
import turtle
t turtle.Turtle()
t.pencolor(blue)
t.pensize(10)
for i in range(4):t.forward(100)t.left(120)
t.hideturtle()
turtle.done() 利用递归画一个螺旋
#内置库,用于画图的模块
import turtle
#实例化turtle对象
my_turtle turtle.Turtle()
#调用窗口
my_win turtle.Screen()def draw_spiral(my_turtle,line_len):if line_len 0:# 向当前方向走line_len 个像素my_turtle.forward(line_len)#箭头向右转90度my_turtle.left(90)#调用自己draw_spiral(my_turtle,line_len - 5)#♥这个图告诉我们递归不一定要有返回值
draw_spiral(my_turtle,300)
my_win.exitonclick() 利用递归画一颗分形树
def tree(branch_len, t):if branch_len 5:t.forward(branch_len)t.right(20)tree(branch_len-15, t)t.left(40)tree(branch_len-15, t)t.right(20)t.backward(branch_len)import turtle
t turtle.Turtle()
my_win turtle.Screen()
t.left(90)
t.up()
t.backward(200)
t.down()
t.color(black)
tree(110,t)
my_win.exitonclick() 利用递归画一个谢尔平斯基三角形
#绘制谢尔平斯基三角形的辅助函数
import turtle
def draw_triangle(points , color, my_turtle ):my_turtle.fillcolor ( color )my_turtle.up()my_turtle.goto(points[0][0],points[0][1])my_turtle.down()my_turtle.begin_fill()my_turtle.goto(points[1][0],points [1][1])my_turtle.goto(points[2][0],points [2][1])my_turtle.goto(points[0][0],points [0][1])my_turtle.end_fill()def get_mid(p1,p2 ):return ((p1[0] p2[0]) / 2 , (p1[1] p2[1]) / 2)# 绘制谢尔平斯基三角形
def sierpinski(points, degree, my_turtle):colormap [blue,red,green,white,yellow,violet,orange,]draw_triangle(points, colormap[degree], my_turtle)if degree 0:sierpinski([points[0],get_mid(points[0], points[1]),get_mid(points[0], points[2]),],degree - 1,my_turtle,)sierpinski([points[1],get_mid(points[0],points[1]),get_mid(points[1],points[2]),],degree - 1,my_turtle,)sierpinski([points[2],get_mid(points[2],points[1]),get_mid(points[0],points[2]),],degree - 1,my_turtle,)def main():my_turtle turtle.Turtle()my_win turtle.Screen()my_points [[-100,-50],[0,100],[100,-50]]sierpinski(my_points, 5, my_turtle)my_win.exitonclick()print(main()) 全文总结
本文主要讲解 本文主要讲解了递归的历史起源以及使用规则 —— 我们通过递归可以将复杂问题简单化,并且我们还学习了如何通过递归进行进制转换,以及如何通过递归去画出我们想要的图形---螺旋图,分形树,谢尔基三角形。 今天的干货分享到这里就结束啦如果觉得文章还可以的话希望能给个三连支持一下Aileen的主页还有很多有趣的文章欢迎小伙伴们前去点评您的支持就我前进的最大动力
