①②③④⑤⑥⑦⑧⑨⑩
Recursion Basic Concepts
recursion
1. Call yourself (short for Russian doll)
2. Recursion
Recursive: Decomposes a recursive problem into several sub-problems of the same size and form as the original problem, which can be solved with the same solution ideas
Return: As the problem continues to shrink, there must be a clear cut-off point (the recursive exit) at which to end the recursion. Once this cut-off point has been reached, the problem can be resolved by returning from the origin to the origin.
Three Principles of Recursion
1. There must be a base condition to exit recursion (baseline condition)
2. Recursive process should approach 1 (recursive condition)
3. Call yourself constantly
Recursive Call Stack (refer to other blogs)
Stack: FIFO (press in and eject)
The stack of recursive calls can be very long, which will take up a lot of memory. If no recursion depth is set, it will exceed the default recursion depth (seems to be default according to the configuration of your computer?) Error will occur and can be avoided by setting the recursion depth
Set Recursion Depth
import sys sys.setrecursionlimit(3000) #Set maximum depth to 3000
Advantages and disadvantages of recursion
Advantage:
1. Compact code
2. Easy to understand
Disadvantages:
1. High time and space consumption
2. Stack overflow may exist
3. Duplicate calculations may exist
Classic Recursive Problem
1. Factorial
n!=n*(n-1)(n-2)(n-3)...321
def factorial(n):
if n == 1:
return 1
else:
return n * factorial(n - 1)
print(factorial(5))
>>>120
2. Calculate the sum,length,max of the list
def sum(list):
if not list:
return 0
else:
return list[0] + sum(list[1:])
def max(list):
assert list, 'list is empty'
if len(list) == 1:
return list[0]
else:
return list[0] if list[0] >= max(list[1:]) else max(list[1:])
# if list[0] >= max(list[1:]):
# return list[0]
# else:
# return max(list[1:])
def len(list):
return 0 if not list else 1 + len(list[1:])
# if not list:
# return 0
# else:
# return 1+len(list[1:])
list = [2, 3, 1, 6, 1, 7]
print(sum(list))
print(max(list))
print(len(list))
3. Yang Hui Triangle
def yanghuitriangle(n):
result = []
if n == 1:
return 1
for index in range(n):
if index == 0 or index == n - 1:
result.append(1)
else:
result.append(yanghuitriangle(n - 1)[index - 1] + yanghuitriangle(n - 1)[index])
return result
print(yanghuitriangle(7))
4. Fibonacci series
The first two numbers have values of 0, 1, or 1, 1, respectively.
Starting with the third number, its value is the sum of the first two numbers;
1 1 2 3 5 8 13 21 34...
def fibonacci(n):
if n == 0 or n == 1:
return n
else:
return fibonacci(n - 1) + fibonacci(n - 2)
print(fibonacci(5))
5. Frog Jump Step
①②③④⑤⑥⑦⑧⑨⑩
Frog jumps up n steps
1. You can skip one or two steps at a time
2. You can skip one or two steps at a time.. or n steps
3.You can skip 1 or 2 steps at a time...or m steps
Be careful:
This is also the case where you need to consider 0.
Calculation process:
f(n-1) is the case when a frog jumps one step
f(n-2) is the case when a frog jumps two steps
...
f(n-n) is the case when a frog jumps N steps
1. You can skip one or two steps at a time
f(n)=f(n-1)+f(n-2)
2. You can skip one or two steps at a time.. or n steps
f(n)=f(n-1)+f(n-2)+f(n-3)+...+f(n-(n-2))+f(n-(n-1))+f(n-n)
That is, f(n)=f(n-1)+f(n-2)+...+f(2)+f(1)+f(0)1
f(n-1)=f(n-1-(1))+f((n-1)-2)+...+f(n-1-(n-2))+f((n-1)-(n-1))
That is, f(n-1)=f(n-2)+f(n-3)+...f(2)+f(1)+f(0)2
Formula 1 and 2 are available:
f(n)=2*f(n-1)
3.You can skip 1 or 2 steps at a time...or m steps
f(n)=f(n-1)+f(n-2)+f(n-3)+...+f(n-(m-2))+f(n-(m-1))+f(n-m)
Organized:
f(n)=f(n-1)+f(n-2)+...+f(n-m+2)+f(n-m+1)+f(n-m) ③
f(n-1)=f(n-1-1)+f(n-1-2)+...f(n-1-(m-2))+f(n-1-(m-1))+f(n-1-m)m
Organized:
f(n-1)=f(n-2)+f(n-3)+...f(n-m+1)+f(n-m)+f(n-m-1) ④
Sorting Formula III Four
f(n)=2*f(n-1)-f(n-m-1)
def frogjump(n):
if n == 0:
return 1
elif n == 1 or n == 2:
return n
else:
return frogjump(n - 1) + frogjump(n - 2)
def frogjump_n(n):
if n == 0:
return 1
elif n == 1 or n == 2:
return n
else:
return 2 * frogjump_n(n - 1)
def frogjump_m(m, n):
if n == 0:
return 1
elif n == 1 or n == 2:
return n
elif m >= n:
return 2 * frogjump_m(m, n - 1)
else:
return 2 * frogjump_m(m, n - 1) - frogjump_m(m, n - m - 1)
print(frogjump(10))
print(frogjump_n(5))
print(frogjump_m(3, 5))
>89
>16
>13
6. Hannotta
The Hannota problem stems from an old Indian legend. According to legend, when the Great Vatican created the world, it made three diamond pillars, on which 64 gold discs were stacked in size from bottom to top. Brahmin was commanded to rearrange the discs from below on another post in order of size. It is also stipulated that at no time can the disc be enlarged on a small disc and that only one disc can be moved between the three columns at a time. What should I do?
def hanni(n, x, y, z):
"""
Steps:
1.If there is only one tower, simply move Disk 1 from the starting tower x Move to Target He z
Otherwise
2.Put disc 1 to n-1 As a whole, from the start tower x With Target Tower z Move to Transfer Tower y
3.Target Tower x Move to Target Tower z
4，Put disc 1 daon-1 As a whole, from the middle tower y With Start Tower x Move to Target Tower z
:param n:Number of layers
:param x: Starting column
:param y: Intermediate column
:param z: Terminal post
:return:
"""
if n==1:
print("{}--->{}".format(x,z))
return
else:
hanni(n-1,x,z,y)
#hanni(1,x,y,z)
print("{}--->{}".format(x, z))
hanni(n-1,y,x,z)
hanni(3,"x","y","z")
>>>>
>x--->z
x--->y
z--->y
x--->z
y--->x
y--->z
x--->z
7. Quick Sort!!! important
basic thought
Quick Sorting uses the idea of dividing and conquering, dividing the column to be sorted into two parts by one-time sorting, one of which records keywords smaller than the other. Then the records of these two parts are sorted separately to achieve the purpose of ordering the whole sequence.
Quick Row Three Steps
(1) Select a benchmark: in the column to be sorted, somehow pick an element as a pivot
(2) Split operation: divide a sequence into two subsequences based on its actual position in the sequence. At this point, the elements on the left side of the datum are smaller than the datum, and the elements on the right side of the datum are larger than the datum.
(3) Quickly sort two sequences recursively until the sequence is empty or has only one element.
How to choose a benchmark
For dividing and conquering algorithms, the efficiency of the dividing and conquering algorithm is maximized when each division can be divided into two equal-length subsequences. That is, the selection of benchmarks is important. The selection of a benchmark determines the length of the two subsequences after the two splits, which in turn has a decisive impact on the efficiency of the entire algorithm. (If the benchmark chosen is not good, the efficiency of fast queuing is low and the time complexity can reach O(n^2)). Generally speaking, the time complexity of fast queuing is O(n*log(n)).
Ideally, the benchmark chosen will divide the sequence to be sorted into two equal-length subsequences
Method (1): Fixed position (generally select first or last)
def quicksort(list):
if len(list) <2:
return list
else:
pivot = list[0]
less = [item for item in list[1:] if item < pivot]
greater = [item for item in list[1:] if item >= pivot]
return quicksort(less) + [pivot] + quicksort(greater)
print(quicksort([3, 8, 2, 6, 9, 10, 1, 24, 12]))
def quick_sort(lists,i,j):
if i >= j:
return list
pivot = lists[i]
low = i
high = j
while i < j:
while i < j and lists[j] >= pivot:
j -= 1
lists[i]=lists[j]
while i < j and lists[i] <=pivot:
i += 1
lists[j]=lists[i]
lists[j] = pivot
quick_sort(lists,low,i-1)
quick_sort(lists,i+1,high)
return lists
print(quick_sort([3, 8, 2, 6, 9, 10, 1, 24, 12],0,len([3, 8, 2, 6, 9, 10, 1, 24, 12])-1))
Binary Tree and Recursion
Take notes after study