施坤的博客
0%

递归算法

发表于 更新于 分类于 阅读次数： Valine：

特点

  • 递归算法是一种直接或者间接地调用自身算法的过程，再计算机编写程序中，递归算法对解决一大类问题是十分有效的。

　　1、递归就是在过程或函数里调用自身。

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

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

　　4、在递归调用的过程中系统为每一层的返回点、局部量等开辟了栈来存储。递归次数过多容易造成栈溢出等。

要求

　　1、每次调用在规模上都有所缩小（通常是减半）；

　　2、相邻两次重复直接有紧密的联系，前一次要为后一次做准备（通常前一次的输出就作为后一次的输入）；

　　3、在问题的规模极小时必须用直接给出解答而不再进行递归调用，因而每次递归调用都是有条件的，无条件的递归将造成死循环而不能正常结束。

实例

  • 循环求余的值大于1，就除以2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def calc(n):
    print("-------------")
    print(n)
    if n/2 >1:
        # print(n)
        res = calc(n/2)
        print('res:',res)
    return n
calc(10)



-------------
10 # 初始化值为10
-------------
5.0 # 第一次循环， 当10/2 >1，进入了第一次调用自己，得到值为5
-------------
2.5 # 第二次循环，当5/2 >1，进入了第一次调用自己，得到值为2.5
-------------
1.25 # 第三次循环，当2.5/2 >1，进入了第一次调用自己，得到值为1.25

# 最终得到三次结果
res: 1.25
res: 2.5
res: 5.0
  • 阶乘
1
2
3
4
5
6
7
8
9
10
def box(n):
    if n <= 0:
        return 1
    else:
        return n*box(n-1)

b = box(2)
print(b)

120