day15.递归函数

一、递归函数

"""

自己调用自己的函数就是递归

递: 去

归: 回

一去一回就是递归

"""

例、

def digui(n):

    print(n,"<====1===>")

    if n > 0:

        digui(n-1)

    print(n,"<====2===>")

digui(5)

代码解析：

"""

# 代码解析:

去的过程:

n = 5 print(5,"<====1===>") 5>0 条件成立-> digui(5-1) => digui(4) 代码阻塞在第13行

n = 4 print(4,"<====1===>") 4>0 条件成立-> digui(4-1) => digui(3) 代码阻塞在第13行

n = 3 print(3,"<====1===>") 3>0 条件成立-> digui(3-1) => digui(2) 代码阻塞在第13行

n = 2 print(2,"<====1===>") 2>0 条件成立-> digui(2-1) => digui(1) 代码阻塞在第13行

n = 1 print(1,"<====1===>") 1>0 条件成立-> digui(1-1) => digui(0) 代码阻塞在第13行

n = 0 print(0,"<====1===>") 0>0 条件不成立 print(0,"<====2===>")

当前这层空间代码已经执行结束

此刻触发回的过程

n = 1 从上一次13行的代码阻塞位置,继续向下执行 print(1,"<====2===>")

n = 2 从上一次13行的代码阻塞位置,继续向下执行 print(2,"<====2===>")

n = 3 从上一次13行的代码阻塞位置,继续向下执行 print(3,"<====2===>")

n = 4 从上一次13行的代码阻塞位置,继续向下执行 print(4,"<====2===>")

n = 5 从上一次13行的代码阻塞位置,继续向下执行 print(5,"<====2===>")

到此,递归函数彻底执行结束.

5 4 3 2 1 0 0 

"""

1、栈帧空间

# 每次调用函数时,在内存中都会单独开辟一个空间,配合函数运行,这个空间叫做栈帧空间

"""

(1).递归是一去一回的过程,

调用函数时,会开辟栈帧空间,函数执行结束之后,会释放栈帧空间

递归实际上就是不停的开辟和释放栈帧空间的过程

每次开辟栈帧空间,都是独立的一份,其中的资源不共享

(2).触发回的过程

    1.当最后一层栈帧空间全部执行结束的时候,会触底反弹,回到上一层空间的调用处

    2.遇到return,会触底反弹,回到上一层空间的调用处,

(3).写递归时,必须给与递归跳出的条件,否则会发生内存溢出,蓝屏死机的情况.

    如果递归层数过多,不推荐使用递归

"""

2、举例

2.1、用递归计算n的阶乘

# 常规方法

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

def func(n):

    total = 1

    for i in range(n,0,-1):

        total *= i

    return total

res = func(5)

print(res)

# 递归写法

def jiecheng(n):

    if n <= 1:

        return 1

    return n*jiecheng(n-1)

res = jiecheng(5)

print(res)

代码解析：

"""

return 后面的表达式,一定是先计算完在返回

# 代码解析:

# 去的过程:

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

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

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

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

n = 1   return 1

# 回的过程:

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

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

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

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

return 5 * 4 * 3 * 2 * 1 => return 120

"""

2.2、尾递归

"""

自己调用自己,并且非表达式

计算的结果要在参数当中完成.

尾递归无论调用多少次函数,都只占用一份空间,但是目前cpython不支持.

"""

def jiecheng(n,endval):

    if n <= 1:

        return endval

    return jiecheng(n-1,endval*n)

res = jiecheng(5,1)

print(res)

代码解析：

"""

# 代码解析:

去的过程

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

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

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

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

n=1 , endval=1*5*4*3*2 return endval

回的过程:

n=2 return 120

n=3 return 120

n=4 return 120

n=5 return 120

因为最后一层空间的返回值就是第一层空间的返回值,所有在使用尾递归的时候

不需要考虑回的逻辑过程,就能解决问题.推荐使用.

"""

链接

巴特西

day15.递归函数

一、递归函数

1、栈帧空间

2、举例

2.1、用递归计算n的阶乘

2.2、尾递归

最新文章

热门文章