递归函数
什么是递归函数
如果函数可以调用自身，则该函数是递归函数。
[En]
If a function can call itself, then the function is a recursive function.
递归就是去，返回就是返回，递归就是往回走的过程。
[En]
Recursion is to go, return is to return, and recursion is the process of going back.
递归函数的条件
一般来说，递归需要 边界条件，整个递归的结构中要有 递归前进段和 递归返回段。当边界条件不满足，递归前进，反之递归返回。就是说递归函数一定需要有边界条件来控制递归函数的前进和返回。
定义一个简单的递归函数
定义一个函数
def recursion(num):
print(num)
if num == 0:
return 'ok'
# 这个函数在自己的作用域中调用自己，这个函数就是一个递归函数
recursion(num-1)
recursion(10)
"""
结果：
10
9
8
7
6
5
4
3
2
1
0
"""
代码解析
我们使用参数10执行这个函数，但是在执行这个函数的过程中，我们再次调用自己，所以现在这个函数将进入第二次第一次调用自己的过程，第一次调用将被暂时阻止。
[En]
We execute this function with an argument of 10, but during the execution of this function, we call ourselves again, so now this function will go into the process of first calling itself for the second time, and the first call will be temporarily blocked.
第二次调用的时候，num-1，参数就变成了9，继续执行，然后就又执行到了调用自己的代码中，现在就会执行第三次调用的过程中，第二次的调用也阻断了；
这就是 递 的过程；
…………
第十一次调用的时候，num-1，层层的嵌套，参数就变成了0，就符合了作用域中的 if num == 0的条件判断式，第十一次的调用就没有再执行到了调用自己的代码，而是彻彻底底的执行完成了 ，然后代码的执行就又回到了第十次的函数调用中。
第十次的函数调用阻断的时候是执行到了 recursion(num-1)，但是这一行代码执行完了，也就是第十一次调用执行完了，并且后面也没有任何代码，所以第十次调用也结束了，然后就回到了第九次调用；然后第八次；再就是第七次，一直到第一次结束，整个函数的执行就结束了；
这就是 归 的过程。
内存栈区堆区
堆栈空间是我们通常所说的STACK，STACK是一个先入后出的空间，正如我们在上面的例子中所说的，我们首先执行函数的第一个调用，但第一个调用由最后一个执行释放，第11个调用是由第一个执行释放的最后一个调用。与堆栈空间的概念相反的是队列空间，它是一个先进、先出、先入、先出的空间，就像我们平时排队一样，第一个队列会比后一个队列先买票，然后当我们学习并发时，我们会详细讨论队列的概念。
[En]
Stack space is what we often call stack, stack is a space with go and go, first in and then out, as we said in the above example, we first execute the first call of the function, but the first call is released by the last execution, and the eleventh call is the last call, which is released by the first execution. Contrary to the concept of stack space is the queue space, which is a first-in, first-out, first-in, first-out space, just as we usually queue up, the first queue will buy tickets first than the later, and then when we learn concurrency, we will talk about the concept of queue in detail.
单独堆栈是一种数据结构，堆栈是先进先出的数据结构，堆排序后是树状数据结构。
[En]
A separate stack is a data structure, the stack is a first-in-first-out data structure, and the heap is a tree-like data structure after sorting.
堆栈区是内存空间，堆栈区是按照先进先出的数据结构，无论是创建还是销毁都是自动为数据分配内存，释放内存，这是系统自动创建的；堆栈区是按照排序的树形数据结构，可以优先取出所需的数据，无论是创建还是销毁都是手动分配内存，释放内存，这是程序员手动编程的。
[En]
Stack area is memory space, stack area is in accordance with the first-in-first-out data structure, whether created or destroyed is automatically allocated memory for data, free memory, which is automatically created by the system; stack area is in accordance with the sorted tree data structure, can give priority to take out the necessary data, whether created or destroyed is manually allocated memory, free memory, which is manually programmed by programmers.
内存空间 特点 内存中的栈区 自动分配，自动释放 内存中的堆区 手动分配，手动释放
当程序在内存中执行时，由于数据类型不同，它将在不同的内存区域中运行。不同的语言有不同的内存分区机制。总的来说，主要有四个方面：
[En]
When the program is executed in memory, it will run in different areas of memory due to different data types. Different languages have different mechanisms for memory partition. Generally speaking, there are four major areas:
- 栈区：分配局部变量空间；
- 堆区：是用于手动分配程序员申请的内存空间；
- 静态区：又称之为全局栈区，分配静态变量，全局变量空间；
- 代码区：又称之为只读区、常量区，分配常量和程序代码空间；
上面的堆栈区、读取区、静态区和代码区都只是内存中的一块空间。
[En]
The stack area, read area, static area, and code area above are all just a piece of space in memory.
死递归
所以当我们使用递归函数时，我们应该注意到，递归函数调用的过程是一个打开和释放堆栈的过程，调用时打开堆栈空间，最后释放堆栈空间，所以，如果打开的空间不结束，它将始终存在，并将始终占用内存空间，但堆栈空间是高级空间，如果新打开的空间不释放。之前的空间不会被释放，所以如果我们打开了很多空间，但是不能释放，那么我们脆弱的内存有足够的空间容纳这么多的堆栈吗？如果没有空间，那么我们的计算机就会爆炸，所以我们在使用递归时应该小心避免这种情况。尤其是死递归。
[En]
So when we use recursive functions, we should note that the process of recursive function calls is a process of opening and releasing stacks, opening up stack space when calling, and releasing stack space at the end, so, if the open space does not end, it will always exist and will always occupy memory space, but the stack space is an advanced space, if the newly opened space is not released. The previous space will not be released, so if we open up a lot of space, but can not release it, then does our weak memory have enough space to accommodate so many stacks? If there is no room, then our computer will explode, so we should be careful to avoid this situation when using recursion. Especially dead recursion.
每次调用函数时，都会在内存族中创建一个单独的空间来与该函数协作。这个空间称为堆栈帧空间。
[En]
Each time a function is called, a separate space is created in the memory family to cooperate with the function. This space is called stack frame space.
1、递归是一去一回的过程，调用函数时，会开辟栈帧空间，函数执行结束之后，会释放栈帧空间，递归实际上就是不停地开辟和释放栈帧空间的过程，每次开辟栈帧空间，都是独立的一份，其中的资源不共享。
2、触发回的过程当最后一层栈帧空间全部执行结束的时候，会触底反弹，回到上一层空间的调用处，遇到return，会触底反弹，回到上一层的调用处
3、写递归时，必须给予递归跳出的条件，否则会发生内存溢出，可能会出现死机的情况，所以当递归的层数过多的时候，不建议使用递归。
Python中的环境递归的层数默认为1000层左右，一般都是996层。
下面的递归函数没有跳出递归条件，所以它是一个死递归，执行看看它是否在1000左右。<details><summary>*<font color='gray'>[En]</font>*</summary>*<font color='gray'>The following recursive function does not jump out of the recursive condition, so it is a dead recursion, execution to see if it is about 1000.</font>*</details>
def recursion(num):
print(num)
recursion(num+1)
recursion(1)
尾递归
简单的来说，在函数返回的时候，调用其本身，并且return语句不包含表达式，这样的一个递归函数就是一个尾递归函数。
换句话说，返回的是函数本身是尾递归函数，递归函数只是调用自己。
[En]
In other words, what is returned is that the function itself is a tail recursive function, and the recursive function simply calls itself.
一般情况下，尾递归在参数中计算。
[En]
In general, the tail recursion is calculated in the parameters.
我们开始的例子是尾递归函数吗？不是，因为在该示例中，这是对您所在省份的调用，但不会返回，因此它仍然是一个普通的递归函数。
[En]
Is the example we started with a tail recursive function? No, because in that example, this is a call to your own province, but it is not returned, so it is still an ordinary recursive function.
使用递归的时候，我们通常在一些技术博客上看到一些关于尾递归优化的东西，这是因为尾递归无论调用多少次函数，都只会占用一份空间，只开辟一个栈帧空间，但是目前 cpython 不支持，然而最常见的解释器就是 cpython 。
Python常见的解释器：cpython、pypy、jpython。
与普通递归相比，尾递归的优点是返回值不需要太多额外的操作。
[En]
The advantage of tail recursion over ordinary recursion is that the returned value does not require too much extra operation.
实例
阶乘计算
正整数的阶乘是小于或等于该数的所有正整数的乘积，而0的阶乘是1。
[En]
The factorial of a positive integer is the product of all positive integers less than or equal to that number, and the factorial of 0 is 1.
""" 循环计算 """
def factorial(num):
if num == 0:
return 1
elif num < -1:
return '只能是零和正整数'
count = 1
for i in range(1, num+1):
count *= i
return count
res = factorial(5)
print(res) # 120
""" 使用普通递归 """
def factorial(num):
if num == 0:
return 1
elif num < -1:
return '只能是零和正整数'
elif num == 1:
return num
return num * factorial(num-1) # 普通函数返回的是一个表达式
res = factorial(5)
print(res) # 120
""" 使用尾递归 """
def factorial(num, count=1):
if num == 0:
return 1
elif num < -1:
return '只能是零和正整数'
elif num == 1:
return count
return factorial(num-1, count*num) # 尾递归返回的是一个函数，计算式在参数中运算
res = factorial(5)
print(res) # 120
斐波那契数列
斐波那契数列是以0、1两个数开头，从这个数列从第3个数开始，每一个数都等于前两树之和。
使用循环解决
def fibonacci(num):
x, y = 0, 1
if num < 1:
return '输入大于0的数字'
elif num == 1:
return 0
elif num == 2:
return 1
for _ in range(num-2):
x, y = y, y+x
return y
res = fibonacci(9)
print(res) # 21
""" 使用普通递归 """
def fibonacci(num):
if num < 1:
return '输入大于0的数字'
elif num == 1:
return 0
elif num == 2:
return 1
return fibonacci(num-1) + fibonacci(num-2)
res = fibonacci(9)
print(res) # 21
""" 使用尾递归 """
def fibonacci(num, x=0, y=1):
if num < 1:
return '输入大于0的数字'
elif num == 1:
return x
elif num == 2:
return y
return fibonacci(num-1, x=y, y=(x+y))
res = fibonacci(9)
print(res) # 21
Original: https://www.cnblogs.com/msr20666/p/16217927.html
Author: 小小垂髫
Title: Python 函数进阶-递归函数
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/499676/
转载文章受原作者版权保护。转载请注明原作者出处！