Python递归原理浅析

这是我参与8月更文挑战的第18天，活动详情查看： 8月更文挑战

1. 递归概述

递归是一种常见解决问题的方法，即把问题逐渐简单化。

递归的基本思想就是 "自己调用自己"，一个使用递归技术的方法将会直接或者间接的调用自己

👉递归结构包括两个部分：

• 定义递归头

  （1）作用：递归的结束条件

  （2）如果没有头，将陷入死循环

• 定义递归体

  （1）作用：满足条件调用自身的方法

👉递归作用：利用递归，可以使用简单的程序来解决一些复杂的问题。比如斐波那契数列的计算、汉诺塔、快速排列等问题。

2. 递归原理

我们在上学期间都学过找规律，给出一组看上复杂的数列，我们可以通过思考计算找到每个数之间的规律后，从而计算得出需要求的数字

同理，递归也类似“找规律”的思想，将一个大问题逐渐分解，直到分解成一个成更小的问题可以被我们简单的解决

我们在前面的学习过程中，Python一切皆是对象，变量位于栈内存，对象位于堆内存

在函数类型函数的存储机制，是使用栈来实现的，栈的特点是先进后出。

递归底层运行过程如下所示：

递归调用过程

1. 程序执行一个函数时，就创建一个新函数栈

2. 函数的局部变量是独立的，不会相互影响

3. 递归必须符合退出递归的条件才行，否则就是无限递归，死循环

4. 当一个函数执行完毕，或者遇到 return，就会返回，遵守谁调用，就将结果返回给谁。

👉递归函数的特点：

(1) 递归就是函数在调用阶段直接或间接的又调用自身。

(2) 在使用递归策略时，必须有一个明确的递归结束条件，称为递归出口。

(3) 递归算法解题通常显得很简洁，但递归算法解题的运行效率较低。所以一般不提倡用递归算法设计程序。

我们通过实现 【案例】阶乘计算 再来理解递归基本原理

首先分析：

（1）阶乘计算公式

factorial(n)
= n! 
= 1 x 2 x 3 x ... x (n-1) x n = (n-1)! x n 
= factorial(n-1) x n
复制代码

（2）递归体：通过上述公式推导，我们可以得到 factorial(n) = factorial(n-1) x n

（3）递归头：n==1作为结束递归的判断条件

def factorical(n):

    if n==1:
        return 1
    else:
        return  n*factorical(n-1)
复制代码

递归的过程为如图所示

3. 递归打印文件目录

使用递归打印指定路径下的所有文件及目录

我们需要使用到前面学习的对文件目录操作的os模块

import os

Pathlist = []

def getpathfile(path,level):

    childFiles = os.listdir(path)
    for file in childFiles:

        filepath = os.path.join(path,file)
        if os.path.isdir(filepath):
            getpathfile(filepath,level+1)
        Pathlist.append("|----"*level+filepath)


for i in reversed(Pathlist):

    print(i)
复制代码

例如我们当前目录结构如下，打印路径下的所有文件和目录运行操作：

Juejin 
| 
|---Tests.txt
|----Tests       
|       |---New
|       |    |--New_test.txt
|       |---old
|       |    |--old_test
|       |    |       |---oldtest.txt
|       |
|----Test 
|       |---test.txt

复制代码

总结

本期，我们学习递归的思想，把复杂的问题通过找到其中一些特定的规律和条件，我们就可以使用最简单方法把问题迎刃而解了。

不管在工作中还是生活中，递归的思想也常常让我们能够用简单方式去解决所遇到困难。

以上是本期内容，欢迎大佬们点赞评论指正，下次见~ღ( ´･ᴗ･` )比心🌹🌹🌹🌹🌹✈️