Technology Sharing

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

The most common understanding of recursion is sequence. The relationship between recursion and sequence is like the relationship between algorithm and data structure.
Like a linear list in a data structure (it can be a sequential list or a linked list, but generally a sequential list), recursion is a
A loop or iterative enumeration process.
Recursion is essentially a mathematical problem, so some students ask whether algorithms require very good math skills. This is not the case. You will find that
These maths are just things we learned a lot in middle school and high school. We have already gone through the college entrance examination, so why should we be afraid of these things!?

1. Fibonacci Sequence

The sequence formed by Fibonacci numbers (usually represented by F(n)) is called the Fibonacci sequence. The sequence starts with 0 and 1, and then
Each number in is the sum of the two numbers before it. That is:

F(0)=0，F(1)=1
F(n)=F(n -1)+ F(n- 2), where n>1, given n(0 ≤n≤ 30), please calculate F(n)

When we get this question, we first look at the scope of the question. It is no more than 30, because the growth rate of Fibonacci numbers is very fast.
It is exponentially fast. So if n is very large, it will exceed the range of 32-bit integer in C language. This is a basic recursive
The deduction and recursive formula have been told to you. What we need to do is to use a loop to implement this recursion.
We just need to use an F[31] array, initialize F[0] and F[1], and then loop the calculation according to the given formula.

int febonacci(int n) {  
    int F[30] = {0,1};  
    for (int i = 2; i < 30; i++) {  
        F[i] = F[i - 1] + F[i - 2];  
    }  
    return F[29]  
}
1
2
3
4
5
6
7

2. Terbonacci sequence

The Tibonacci sequence Tn is defined as follows:
T(0) = 0, T(1) = 1,T(2)=1
And under the condition that n>2, T(n)=T(n-1)+T(n-2)+T(n-3), given an integer n, please return the nth Tibonacci
The value of the number T(n).
If you already understand the Fibonacci sequence, then this problem is not difficult. However, you need to initialize the first three numbers.
And when the loop iterates, the current value needs to be the sum of the previous three values. Like this:

int tribonacci(int n) {  
    int F[30] = {0,1,1};  
    for (int i = 3; i < 30; i++) {  
        F[i] = F[i - 1] = F[i - 2] + F[i - 3];  
    }  
    return F[29];  
}
1
2
3
4
5
6
7

3. Two-dimensional recursion problem

Problems like the Fibonacci sequence are solved by a one-dimensional array. Sometimes, when one dimension cannot solve the problem, I
We need to look at the problem from a higher dimension.

The length is n(1
But there must be no other characters) and it is forbidden to have M adjacent to each other. How many types of such strings are there?

Consider a string of length n, with f[n][0] ending in 'A', f[n][1] ending in 'C', and f[n][2] ending in ''.
f[n][2]

4. Actual combat

4.1 Fibonacci Numbers

Fibonacci Numbers(Usually useF(n)The sequence formed byFibonacci Sequence. This sequence is composed of0and1Initially, each subsequent number is the sum of the two preceding numbers.

int fib(int n){
    if(n == 0){
       return 0;

    }
    else if (n == 1){
        return 1;

    }
    return fib(n - 1) + fib(n - 2);
}
1
2
3
4
5
6
7
8
9
10
11

4.2 Likou 70 Stair Climbing

Suppose you are climbing stairs.nYou can reach the top of the building by climbing the stairs.
Every time you can climb1or2How many different ways can you get to the top of the building?

int climbStairs(int n) {  
    int f[46];  
    f[0] = 1;  
    f[1] = 1;  
    for(int i = 2; i <= n; i++){  
        f[i] = f[i - 1] + f[i - 2];  
    }  
    return f[n];  
}
1
2
3
4
5
6
7
8
9

4.3 Likou 119 Yang Hui Triangle ||

Given a non-negative indexrowIndex, return to the firstrowIndexOK.

int* getRow(int rowIndex, int* returnSize) {  
    int f[34][34];  
    for(int i = 0; i <= rowIndex; i++){  
        for(int j = 0; j <= i; j++){  
            if(j ==0 || j == i){  
                f[i][j] = 1;  
            }  
            else {  
                f[i][j] = f[i - 1][j] + f[i - 1][j - 1];   
            }  
        }  
    }  
    int* ret = (int *)malloc (sizeof(int) * (rowIndex + 1));  
    for(int j = 0; j <= rowIndex; j++){  
        ret[j] = f[rowIndex][j];  
    }  
    *returnSize = rowIndex + 1;  
    return ret;  
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19