How to better understand recursive algorithms? Detailed explanation of Python examples

Recursion is indeed a relatively abstract mathematical logic, which can be simply understood as "the program calls its own algorithm."

Wikipedia’s explanation of recursion is:

Recursion (English: Recursion), also translated as recursion, in mathematics and computer science, refers to using the function itself in the definition of the function Methods. The term recursion is also more commonly used to describe the process of repeating things in a self-similar way.

For example, when two mirrors are approximately parallel to each other, the images nested in the mirrors appear in the form of infinite recursion. It can also be understood as the process of self-replication.

"Pass" means to pass, and "Return" means to return. First pass a method layer by layer, then pass it to the last layer and return the result back.

For example, I queued up for a nucleic acid test, and there were 100 people in front of me. I wanted to ask what time the medical staff would get off work, so I asked the brother in front of me, and he asked again. The people in front of him passed it on one by one, and finally passed it to the medical staff, who replied that they would get off work at 6 p.m. This sentence was passed back and finally reached me. I learned that the medical staff got off work at six o'clock.

This process is a recursive process. If "passing a message" itself is a method, then the entire process of transmitting a message is calling its own method, and finally obtains the result.

This is different from the cycle. The cycle is equivalent to putting headphones on everyone, and then an "intermediary" will ask you one by one if you know what time the medical staff will get off work. When you ask the medical staff, , got the answer, the "agent" told me to get off work at six o'clock.

In essence, recursion is to continuously dismantle a big problem, like peeling an onion, and finally dismantle it to the smallest level, and return the solution result.

Use Python to give the simplest example of a recursive function and talk about what recursive applications are.

We often see functions calling themselves to implement loop operations, such as functions for finding factorials.

The factorial of the integer n is n*(n-1)*(n-2)*...*3*2*1.

The following 5 lines of Python code can realize the calculation of factorial.

def fact(n):
''' n表示要求的数的阶乘 '''
if n==1:
return n 
n = n*fact(n-1)
return n
print(factorial(5))

Many people may be confused about the calculation logic here, why the fact function calls itself and finally gets the result.

We can deduce according to mathematical logic:

The factorial of the integer n is: fact(n) = n*(n-1)*...*3*2*1.

The factorial of the integer n-1 is: fact(n-1) = (n-1)*(n-2)*...*3*2*1.

So it can be inferred that fact(n) = n*fact(n-1).

Is there a fact method that can be called for each number? When n=1 is finally called, the factorial of the result n is returned.

Look at the picture above, the recursive function will be called layer by layer, and finally when n=1, the result will be returned upward.

This is the whole process of recursion. If we give an accurate definition of recursion, it can be summarized as the following three points:

1. There is at least one clear end condition for recursion.

2. Give the solution when recursion terminates.

3. Each time you enter a deeper level of recursion, the problem size (calculation amount) should be reduced compared to the last recursion.

Take the above code as an example:

def factorial(n):
''' n表示要求的数的阶乘 '''
if n==1: # 1、明确递归终止条件；
return n # 2、递归终止时的处理办法
n = n*factorial(n-1) # 递去
return n# 归来

In addition to common factorial cases, there are also Fibonacci sequences, which are also classic uses of recursion.

Fibonacci Sequence: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89...

This sequence starts from the 3rd item, Each term is equal to the sum of the previous two terms.

It is defined recursively as follows: F(0)=0, F(1)=1, F(n)=F(n - 1) F(n - 2)(n ≥ 2, n∈ N*).

In Python, we can use recursive functions to implement the Fibonacci sequence:

# 1，1，2，3，5，8，13，21，34，55，试判断数列第12个数是哪个？
def fab(n):
''' n为斐波那契数列 '''
if n <= 2:
v = 1
return v 
v = fab(n-1)+fab(n-2) 
return v

print(fab(12)) 

Use mathematical methods to derive:

• fab(0 ) = 0 (initial value).
• fab(1) = 1(initial value).
• For all integers n greater than 1: fab(n) = fab(n-1) fab(n-2) (recursive definition).

In fact, the above two recursive cases can be explained by mathematical induction, which is the knowledge of high school mathematics.

Generally, to prove a proposition P(n) related to a natural number n, there are the following steps:

(1) Prove that the proposition is true when n takes the first value n0. n0 takes the value 0 or 1 for general sequences, but there are also special cases.

(2) Assume that the proposition is true when n=k (k≥n0, k is a natural number), and prove that the proposition is also true when n=k 1.

Based on (1) (2), for all natural numbers n (≥n0), the proposition P(n) is true.

In addition to mathematical explanations, I have also seen someone give a more vivid explanation of recursion before:

1、我们已经完成了吗?如果完成了，返回结果。如果没有这样的终止条件，递归将会永远地继续下去。

2、如果没有，则简化问题，解决较容易的问题，并将结果组装成原始问题的解决办法。然后返回该解决办法。

哈哈,到这里大家是不是对递归有了一个更加深刻的认识。

如果还不清楚，没关系，这里还有更多的递归案例，用Python来实现，可以说非常简洁。

「最大公因数：」

def gcd(m, n):
if n == 0:
return m
else:
return gcd(n, m%n)

「从 1 到 n 的数字之和：」

def sumnums(n):
if n == 1:
return 1
return n + sumnums(n - 1)

print(sumnums(3))

「字符串倒序：」

def reverse(string):
if len(string) == 0:
return string
else:
return reverse(string[1:]) + string[0]

reverseme = '我是帅哥'
print(reverse(reverseme))

「汉诺塔问题：」

def towerOfHanoi(numrings, from_pole, to_pole, aux_pole):
if numrings == 1:
print('Move ring 1 from', from_pole, 'pole to', to_pole, 'pole')
return
towerOfHanoi(numrings - 1, from_pole, aux_pole, to_pole)
print('Move ring', numrings, 'from', from_pole, 'pole to', to_pole, 'pole')
towerOfHanoi(numrings - 1, aux_pole, to_pole, from_pole)
numrings = 2
towerOfHanoi(numrings, 'Left', 'Right', 'Middle')

「二分法找有序列表指定值：」

data = [1,3,6,13,56,123,345,1024,3223,6688]
def dichotomy(min,max,d,n):
'''
min表示有序列表头部索引
max表示有序列表尾部索引
d表示有序列表
n表示需要寻找的元素
'''
mid = (min+max)//2
if mid==0:
return 'None'
elif d[mid]<n:
print('向右侧找！')
return dichotomy(mid,max,d,n)
elif d[mid]>n:
print('向左侧找！')
return dichotomy(min,mid,d,n)
else:
print('找到了%s'%d[mid])
return 
res = dichotomy(0,len(data),data,222)
print(res)

有位大佬说过：To Iterate is Human, to Recurse, Divine。

中文译为：人理解迭代，神理解递归。

可见递归是非常神奇的算法，它的神奇之处在于它允许用户用有限的语句描述无限的对象。

当然人无完人，递归也是有缺点的，它一般效率较低，且会导致调用栈溢出。

因为递归不断调用自身函数，且产生大量变量，而栈空间的容量是有限的，循环太多就会效率低下，甚至导致调用栈溢出。

The above is the detailed content of How to better understand recursive algorithms? Detailed explanation of Python examples. For more information, please follow other related articles on the PHP Chinese website!