python 递归函数

钢铁小花

【需求】：求教各位技术大佬传授递归函数的学习方法？


【背景】：在自学python，具备一些基本的数据结构和算法知识。当前最大的问题是递归函数这块，
【问题】：那种比较简单的递归函数问题，比如求阶乘，求斐波那契数列，小青蛙蹦台阶之类的，都能理解，自己也写一些简单的递归函数来解决问题；
但是，一遇到那种连续两行都是递归函数的代码（比如二叉树里面的遍历问题）就晕了，不知所以，感觉看懂了（实际上不懂），能对着树结构理解遍历的顺序，但是对着代码就不能很好的理解每一步到哪了；或者是类似“用L型砖铺缺一个角棋盘”的问题，知道把问题缩小规模，但是用递归自己完全写不出来，脑壳疼，
哎，死抠也抠不出所以然来，反复看书，搜帖子，视频教程也没找到什么靠谱的办法~~~不知道该从哪努力，想着论坛里大佬多，兴许金手指一指，就醍醐灌顶了~~~

845xyz

递归我懂 问题我没看懂 哈哈哈哈 还要好好学学

2Burhero

递归有什么难的

v.n.lee

我连你的提问都看不懂，反正我是真的不会，上次写爬虫要用到，死活写不出来

大脑组织残缺

把递归理解成一个栈，调用就是入栈，返回就是出栈。
所以递归与非递归算法的转换基本上都是通过栈实现的。
最好的办法就是 拿根笔，拿张纸，把递归的流程模拟着画一下，之后在使用递归就不觉得逻辑特别乱了
好像说用递归算法 也是计算机系统自动生成的堆栈，cpu会不停的中断请求命令跳转之类的导致效率不高，复杂问题不如自己创建栈用非递归。

buerse

看不懂你的问题

钢铁小花

v.n.lee 发表于 2019-12-26 16:54
我连你的提问都看不懂，反正我是真的不会，上次写爬虫要用到，死活写不出来

是我描述的不够清晰，我应该把代码贴上来

钢铁小花

buerse 发表于 2019-12-26 22:35
看不懂你的问题

是我描述的不够清晰，我应该把代码贴上来。比如这道题，8个人本来对应8个座位，但是它们有自己想去的位置，M[0]表示人a想去的座位号是c。除非换到自己喜欢的座位，否则这些人不愿意挪位置。求满足最多人数心愿的排列。看不懂递归部分…………
# 寻找最大排列
#a=0,b=1,c=2,d=3,e=4,f=5,g=6,h=7
M = [2, 2, 0, 5, 3, 5, 7, 4] # people want to go
def naive_max_perm(M, A=None): # A：剩余人员的集合；
    if A is None:
        A = set(range(len(M))) # A = {0, 1, 2, ...,n-1}
    if len(A) == 1:
        return A
    B = set(M for i in A) # the "pointed to" elements
    C = A - B
    if C:
        A.remove(C.pop())
        return naive_max_perm(M, A)
    return A

naive_max_perm(M)

钢铁小花

大脑组织残缺 发表于 2019-12-26 21:12
把递归理解成一个栈，调用就是入栈，返回就是出栈。
所以递归与非递归算法的转换基本上都是通过栈实现的。 ...

写着写着就晕了

大脑组织残缺

钢铁小花 发表于 2019-12-27 13:50
写着写着就晕了

可以这样，就拿树的递归遍历来说
画个两层的树，捋一下逻辑
再画个三层的，捋一下逻辑
再画个四层的，捋一下逻辑
找张大纸，再来个六层的
这一趟下来过两天要是还觉得递归头晕，就别用递归了...