Python面试常见算法题集锦（递归部分）

0x1 前言

开始学习python基础的时候，有以下几种算法是面试中常见的，也是前期学习python的时候可以连带学习了解的，不卡门槛哟

0x2 实现算法的方式很多种，而算法的实现也是分程序语言的，此处用python

1.用python写一个简单的递归函数

分析：

递归函数 : 自己调用自己的函数是递归函数
递:去
归:回

触发回的过程有2个条件: 回到上一层函数调用的位置
(1) 当前这层空间函数全部执行结束的时候,触底反弹,触发回的过程
(2) 遇到return 返回值, 直接返回到上一层空间
(3) 递归: 去的过程:就是不停的开辟空间,在回的时候,不停的释放空间,递归函数就是不停的开辟和释放空间的过程
回过程:最后一层空间所有代码执行完毕,会触发回的过程,或者遇到return返回值,也会触发回的过程,回到上一层函数调用的位置

注意事项:
1.递归每一层空间都是独立的个体,独立的副本,资源不共享,可以通过参数或者返回值形成共享
2.递归务必给予跳出的条件,如果递归的层数过深,不推荐使用.容易内存溢出或者蓝屏;

代码：

def digui(n):

    """

    打印1111,2222 是为了使读者看的更清楚 去 回  的两个过程区分

    """

    if n > 0:

        print(n, "1111111")

        digui(n - 1)

    print(n, "2222222")

digui(5)

# 分析

"""

5 1111111

4 1111111

3 1111111   去

2 1111111

1 1111111

0 2222222

1 2222222

2 2222222

3 2222222    回

4 2222222

5 2222222

"""

2.求任意数n的阶乘 5! 5x4x3x2x1=?

def jiecheng(n):

    if n <= 1:

        return 1

    return n * jiecheng(n - 1)

res = jiecheng(5)

print(res)

# 代码解析:

# 去的过程

"""

n = 5 return n*jiecheng(n-1) => 5*jiecheng(4)

n = 4 return n*jiecheng(n-1) => 4*jiecheng(3)

n = 3 return n*jiecheng(n-1) => 3*jiecheng(2)

n = 2 return n*jiecheng(n-1) => 2*jiecheng(1)

n = 1 return 1

"""

# 回的过程

"""

n = 2 return n*jiecheng(n-1) => 2*1

n = 3 return n*jiecheng(n-1) => 3*2*1

n = 4 return n*jiecheng(n-1) => 4*3*2*1

n = 5 return n*jiecheng(n-1) => 5*4*3*2*1

"""

# 5*4*3*2*1 = 120

3.斐波那契数列: 1,1,2,3,5,8,13,21,34,55 ,… 第n个数字是几?

def fbnq(n):

    if n == 1 or n == 2:

        return 1

    return fbnq(n - 1) + fbnq(n - 2)

res = fbnq(5)

print(res)

# 代码解析

"""

斐波那契数列简单地说，起始两项为0和1，此后的项分别为它的前两项之和

F（0）=0，F（1）=1，F（n）=F(n-1)+F(n-2)（n≥2，n∈N*）

fbnq(5) = fbnq(4) + fbnq(3) = fbnq(3) + fbnq(2) + fbnq(3) => fbnq(2) + fbnq(1) + fbnq(2) + fbnq(2) + fbnq(1)

        => 1+1+1+1+1 = 5

"""

巴特西