python 函数递归

前言：

  递归真的很重要，之前学的时候，学的一知半解，以为真正了解，每次想到递归，就记得一句：返回给函数的调用者，嗯？函数调用者，你是说外部，还是内部啊？疑问太多了，还有就是被告知一句：递归能解决的问题，循环都能解决，所以就更加不重视递归了！直到接触算法后，在解决问题时，最快，最容易理解的解法就是递归，但是此时的递归却是看不太懂为什么要这样做！我先来说下，在算法中遇到可以用递归轻松完成的：希尔排序、归并排序、快速排序、反转链表及各种反转问题、二叉树的深度遍历、二叉树的各种题基本可以用、全排列…还有算法步骤里需要用到，太多了，所以，递归非常重要！“To iterate is human, to recurse divine 迭代是人，递归是神”，接下来，我也是看了很多算法书和视频，重点来整理下递归！

一 函数递归调用介绍

  • 首先“递归”包括两个过程：递“去”的过程，“归”回的过程！先从一个简单的递归函数讲起
  • def di_gui(n):
    print(n, "<===1====>")
    if n > 0:
        di_gui(n - 1)
    print(n, '<===2====>')


di_gui(5) # 外部调用后打印的结果是？

    函数不仅可以嵌套定义，还可以嵌套调用，即在调用一个函数的过程中，函数内部又调用另一个函数，而函数的递归调用指的是在调用一个函数的过程中又直接或间接地调用该函数本身.

  • 递归的执行过程：首先，递归会执行“去”的过程，只需要满足终止条件，就会一直在函数内，带着更新的参数，调用函数自身，注意：到内部调用函数， 以下面的代码不会被执行，而是暂停阻塞；此时 随着函数每调用一次自身，还没有触发 返回值和到达终止条件，等同于在原来的基础上不断“向下/向内”开辟新的内存空间，记住，每次调用一次函数，就不是处在同一空间（想象下《盗梦空间》里的情景，梦中梦，都是处于不同的空间）

                                                                     

  •  什么时候“递”去的过程结束？记住有两种情况>>> 一是：当前这层空间函数全部执行结束（终止条件），二是：执行到了return 返回值，直接返回；

二 回溯与递推

　　举个列子：某公司四个员工坐在一起，问第四个人薪水，他说比第三个人多1000，问第三个人薪水，第他说比第二个人多1000，问第二个人薪水，他说比第一个人多1000，最后第一人说自己每月5000，请问第四个人的薪水是多少？

　　思路：要知道第四个人的月薪，就必须知道第三个人的，第三个人的又取决于第二个人的，第二个人的又取决于第一个人的，而且每一个员工都比前一个多一千.

代码示例：

salary(4)=salary(3)+1000 
salary(3)=salary(2)+1000 
salary(2)=salary(1)+1000 
salary(1)=5000
总结为： 
salary(n)=salary(n-1)+1000 (n>1) 
salary(1)=5000 (n=1)

可以将该过程分为两个阶段：回溯和递推。

                                                                     

　　在回溯阶段，要求第n个员工的薪水，需要回溯得到(n-1)个员工的薪水，以此类推，直到得到第一个员工的薪水，此时，salary(1)已知，因而不必再向前回溯了。然后进入递推阶段：从第一个员工的薪水可以推算出第二个员工的薪水(6000)，从第二个员工的薪水可以推算出第三个员工的薪水(7000)，以此类推，一直推算出第第四个员工的薪水(8000)为止，递归结束。需要注意的一点是，递归一定要有一个结束条件，这里n=1就是结束条件。

代码实现：

def salary(n):
    if n==1:
        return 5000
    return salary(n-1)+1000

s=salary(4)
print(s)

　　从内存角度（本质）来分析：每调用一次函数，都会单独开辟一份栈帧空间，递归函数就是不停的开辟和释放栈帧空间的过程，具体来理解下：一个普通函数从执行到结束，就是一个开辟空间和释放空间的过程；而递归函数是在调用最外层函数时，先开辟一个最外层空间，每调用一次自身，就会在最外层空间内，再自己开辟本次的空间（所以递归耗内存）（还有一种说法是，不断的本次空间的基础上再开辟空间，等于是不断的嵌套，其实这两种说法本质上是一样的，因为信息都可以做到不共享），空间之间如果不通过参数传递或者用return 返回值，信息是不共享的.

  • 递归的数据共享情况：递归每一层间的数据是独立的，不共享，但是可以通过参数或者返回值来形成共享，参数具体在传入的是“引用类型”（比如列表）

  • 递归 必须要有一个出口，如果没有出口就会重复调用，不断的开辟栈帧空间

　　递归本质就是在做重复的事情，所以理论上递归可以解决的问题循环也都可以解决，只不过在某些情况下，使用递归会更容易实现，比如有一个嵌套多层的列表，要求打印出所有的元素，代码实现如下：

items=[[1,2],3,[4,[5,[6,7]]]]
def foo(items):
    for i in items:
        if isinstance(i,list): #满足未遍历完items以及if判断成立的条件时，一直进行递归调用
            foo(i) 
        else:
            print(i,end=' ')

foo(items) #打印结果1 2 3 4 5 6 7

使用递归，我们只需要分析出要重复执行的代码逻辑，然后提取进入下一次递归调用的条件或者说递归结束的条件即可，代码实现起来简洁清晰.

想要学的更加细腻，牵扯到底层的原理，请看：

https://blog.csdn.net/storyfull/article/details/102671946?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522161717712916780274142650%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fall.%2522%257D&request_id=161717712916780274142650&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~first_rank_v2~hot_rank-2-102671946.first_rank_v2_pc_rank_v29&utm_term=python%E9%80%92%E5%BD%92
python从0开始

相关

标签