Recursive Classic Algorithms


Recursion Basic Concepts


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

1. Compact code
2. Easy to understand
1. High time and space consumption
2. Stack overflow may exist
3. Duplicate calculations may exist

Classic Recursive Problem

1. Factorial


def factorial(n):
    if n == 1:
        return 1
        return n * factorial(n - 1)

2. Calculate the sum,length,max of the list

def sum(list):
    if not list:
        return 0
        return list[0] + sum(list[1:])

def max(list):
    assert list, 'list is empty'
    if len(list) == 1:
        return list[0]
        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]

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(yanghuitriangle(n - 1)[index - 1] + yanghuitriangle(n - 1)[index])
    return result


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
        return fibonacci(n - 1) + fibonacci(n - 2)

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

2. You can skip one or two steps at a time.. or n steps
That is, f(n)=f(n-1)+f(n-2)+...+f(2)+f(1)+f(0)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:

3.You can skip 1 or 2 steps at a time...or m steps
f(n)=f(n-1)+f(n-2)+...+f(n-m+2)+f(n-m+1)+f(n-m) ③

f(n-1)=f(n-2)+f(n-3)+...f(n-m+1)+f(n-m)+f(n-m-1) ④

Sorting Formula III Four

def frogjump(n):
    if n == 0:
        return 1
    elif n == 1 or n == 2:
        return n
        return frogjump(n - 1) + frogjump(n - 2)

def frogjump_n(n):
    if n == 0:
        return 1
    elif n == 1 or n == 2:
        return n
        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)
        return 2 * frogjump_m(m, n - 1) - frogjump_m(m, n - m - 1)
print(frogjump_m(3, 5))

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):
    1.If there is only one tower, simply move Disk 1 from the starting tower x Move to Target He z
    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
    if n==1:
        print("{}--->{}".format(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
        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
        while i < j and lists[i] <=pivot:
            i += 1
    lists[j] = pivot
    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

Tags: Algorithm Python programming language

Posted by compound_eye on Fri, 12 Aug 2022 22:02:54 +0530