【我和Python算法的初相遇】——体验递归的可视化篇

用户10920432

发布于 2024-01-18 18:05:45

1550

发布于 2024-01-18 18:05:45

递归的起源

递归是一种算法，它利用函数的自身调用来解决问题。递归的历史可以追溯到古代的数学家和逻辑学家，如希腊哲学家亚里士多德和印度数学家阿耶尔巴塔。然而，递归算法的实际应用可以追溯到早期的计算机科学，尤其是在20世纪40年代和50年代的计算机发展初期。

在20世纪初，数学家David Hilbert提出了“希尔伯特问题”，其中包括一个著名的问题——哥德尔不完备定理。这个定理表明，任何一个形式化的系统都无法证明自身完备。这导致了一些数学家开始研究递归函数，因为递归函数是一种强大的工具，可以用来刻画数学中的可计算性概念。在20世纪40年代，递归理论被广泛研究，它为计算机科学的发展奠定了基础。

早期计算机（如ENIAC）是通过执行单个指令来执行操作的，因此递归算法在这些机器上的执行效率较低。然而，随着计算机硬件和编程语言的发展，递归算法变得更加普遍和有效。今天，递归算法被广泛用于计算机科学中的许多应用领域，如数据结构设计、图像处理、机器学习和自然语言处理。

什么是递归?

递归是一种解决问题的方法，其精髓在于将问题分解为规模更小的相同问题持续分解，直到问题规模小到可以用非常简单直接的方式来解决。 递归的问题分解方式非常独特，其算法方面的明显特征就是:在算法流程中调用自身。 递归为我们提供了一种对复杂问题的优雅解决方案，精妙的递归算法常会出奇简单令人赞叹。

问题:

给定一个列表，返回所有数的和列表中数的个数不定，需要一个循环和一个累加变量来迭代求和

def Listsum(nl):
    sum = 0
    for i in nl:
        sum += i
    return sum

print(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 = "0123456789"
    if 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())