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.斐波那契数列: 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)

代码解析：

可以转化为斐波那契数列的方式进行求解，假设要跳N阶台阶，那么第一步有两种跳法：
（1）跳一步，后面还有n-1个台阶需要跳；
（2）跳两步，后面还有n-2个台阶需要跳。
可以看到跳n阶台阶的跳法数等于跳n-1和n-2阶台阶数的和，即F(n) = F(n-1) + F(n-2)

4.青蛙跳台阶: 一只青蛙要跳上n层高的台阶,一次能跳一级,也可以跳两级,请问这只青蛙有多少种跳上这个n层高台阶的方法?

代码：

def Frog_JumpSteps_digui(n):
    if n in (1, 2):
        return 1
    return Frog_JumpSteps_digui(n - 1) + Frog_JumpSteps_digui(n - 2)


res = Frog_JumpSteps_digui(2)
print(res)

代码解析：

可以转化为斐波那契数列的方式进行求解，假设要跳N阶台阶，那么第一步有两种跳法：
（1）跳一步，后面还有n-1个台阶需要跳；
（2）跳两步，后面还有n-2个台阶需要跳。
可以看到跳n阶台阶的跳法数等于跳n-1和n-2阶台阶数的和，即F(n) = F(n-1) + F(n-2)