There are a ton of recursion explanations out there, and it's a headache trying to understand the key and not getting it. I wanted to write a way for myself to make it simple for you to understand, in a straight-forward way.Connection between "code" and "method"。
1. Problem: Fibonacci (summing operations)
Find the sum of the numbers up to 4
2. Problem-solving methods
Example of Fibonacci series (The values are 1, 1, 2, 3, 5, 8, 13, 21, 34 ...... In math, this number series starts with recursive (calculation) The method definition of theF(0)=0，F(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N*））
Simple to understand The formula can be written, sum = (1+ ( 2+ ( 3+4)))
3.Code realization
3.1 Recursive Code Implementation
1 def digui(n): 2 if n == 0: # Base case (boundary conditions) 3 return 0 4 else: 5 return n + digui(n-1) # Recursive steps, function: recursion, return: return 6 print(digui(4))
Code Result Output : 10
"Recursion" line 5 code here you think of it as a math problem with parentheses, there are parentheses first counting parentheses, until there are no parentheses, the value of the operation inside the parentheses in the operation with the value of the parentheses, as shown in the figure
This code would look like this if it was represented by a stack, as shown here
The order in which the stack is stored:
During each recursive call, the contents of the stack will look like this:
1 | | <- Top of Stack 2 | digui(0) | <- this function completes and returns 0 3 | digui(1) | <- 1 + digui(0) 4 | digui(2) | <- 2 + digui(1) 5 | digui(3) | <- 3 + digui(2) 6 | digui(4) | <- 4 + digui(3)
3.2 Loop Code Implementation
1 def xunhuan(n): 2 result = 0 3 for i in range(1, n+1): # Cyclic accumulation from 1 to n 4 result += i 5 return result 6 7 print(xunhuan(4))
Code Result Output : 10