python 算法 day2

递归 RECURSION

递归是一种解决问题的方法，把问题划分成越来越小的子问题，直到问题的规模小到可以被简单解决。

计算数字列表的和，

def list_sum(num_list):
    the_sum = 0
    for i in num_list:
        the_sum = the_sum +i
    return the_sum
print(list_sum([1,3,5,7,9]))

我们可以利用全括号的表达式来重新表示列表：((((1+3)+6)+8)+5)

我们也可以从另一个方向来添加括号：(1 + (3 +(6 +(8 +5))))

求和问题变成如下：

listSum(numlist) = first(numlist) + listSum(rest(numLIst))

first 代表列表中的第一个元素而rest代表列表中除了第一个元素以外的其他所有元素

使用迭代实现：

def list_sum(num_list):
    if len(num_list) ==1:
        return num_list[0]
    else:
        return num_list[0] + list_sum(num_list[1:])

print(list_sum([1,3,5,7,9]))

递归函数就是一种调用自身的函数，可以将这一系列的递归调用看做一次次简化问题的过程。每次进行递归调用过程就是在解决一个规模更小的问题,当问题的规模达到最小时结束递归。

递归三大定律

递归算法必须有个基本结束条件
递归算法必须改变自己的状态并向基本结束条件演进
递归算法必须递归地调用自身

将整数转化成任意进制表示的字符串形式

列如：把整数10转换成二进制数 "1010“ 确定进位数之后整个算法将包含三个部分：

1）将原始整数分解成一连串的单个数字

2）通过在字符序列中检索将单个数字转换成字符串

3）将这些单个数字的字符串连接起来，形成最终的结果

用整数的除法将 769 除以 10,我们得到 76 余 9。这给了我们两个好的结果。
首先,余数是一个小于进位数的数字,通过检索,它可以直接转换成一个字符。

第二,我们得到了一个小于初始数字的新数字"76",它能让我们向着“找到小于进位数的单个数字”的基本结束条件演进。现在我们的任务是再将 76 转换为它的字符串形式。我们将再一次使用除法取余得运算,这样分别得到 7 和 6.

最后,我们将问题简化为转换数字 7 为字符串形式,因为它满足基本结束条件“n<base,base=10”,我们可以很容易转化。我们刚才的一系列操作如图所示。注意,我们想要记住的数字在图示右侧的余数方框中。

def to_str(n,base):
    convert_string = "0123456789ABCDEF"
   
    if n < base:
        return convert_string[n]
    else:
        return to_str(n//base,base) + convert_string[n %base]
        #取整和取余 

print(to_str(48,16))

函数,接受一个字符串作为参数,并返回一个反向的新字符串

def reverse(list):
    print(list)
    if len(list)>1:
        return reverse(list[1:]) + list[0]
    else:
        return list[0]

print(reverse('boypp'))

栈帧：实现递归

from pythonds.basic.stack import Stack
r_stack = Stack()
def to_str(n,base):
    convert_string = '0123456789ABCDEF'
    while n>0:
        if n<base:
            r_stack.push(convert_string[n])
        else:
            r_stack.push(convert_string[n%base])
        n = n//base
    res = ""
    while not r_stack.isEmpty():
        res = res + str(r_stack.pop())
    return res
print(to_str(48,16))

在python中，当一个函数被调用时，系统会分配一个栈帧去处理函数那些局部变量。当执行完函数时，并得到一个返回值，这个值会被留在栈顶等待被调用的函数来处理

图示递归：

import turtle
myTurtle = turtle.Turtle()
myWin = turtle.Screen()

def drawSpiral(myTurtle, lineLen):
    if lineLen > 0:
        myTurtle.forward(lineLen)
    myTurtle.right(90)
    drawSpiral(myTurtle,lineLen - 5)
drawSpiral(myTurtle,100)
myWin.exitonclick()

通过递归的方法来画一个螺旋线，运行上述代码如果遇到ModuleNotFoundError: No module named 'tkinter'

在python3下

sudo apt-get install python3-tk

通过递归画出分形树，分形：无论你如何放大图形，你所看到的每一个区域中的碎片形状都和原来的形状相同



def tree(branchLen , t):
    if branchLen > 5:
        t.forward(branchLen)
        t.right(20) #主分叉
        tree(branchLen-5,t)
        t.left(40)  #二次分叉
        tree(branchLen-10,t)
        t.right(20) #三次分叉
        t.backward(branchLen)

def main():
    t =turtle.Turtle()
    mywin = turtle.Screen()
    t.left(90)
    t.up()
    t.backward(100)
    t.down()
    t.color("green")
    tree(75,t)
    mywin.exitonclick()
main()