From “mathematical induction” to understanding “recursive algorithms”!

A little positivity in each chapter: a person’s life may burn or decay.

preface

I believe you will occasionally encounter questions or programming about recursive algorithms in your interview or work, so today we are going to talk about things from mathematical induction to understanding recursive algorithms. If there are mistakes, please point out in time

This article has been synchronized to GitHub/Gitee/ public account, interested students help click to follow ~

1. Mathematical induction

1.1 introduction

Source baidu Baike

Mathematical Induction (MI) is a Mathematical proof usually used to prove that a given statement is true over the whole (or local) range of natural numbers. In addition to natural numbers, mathematical induction in a broad sense can also be used to prove general well-base structures, such as trees in set theory. This generalized mathematical induction is used in mathematical logic and computer science and is called structural induction. In number theory, mathematical induction is a mathematical theorem that proves in a different way that any given situation is true (the first, the second, the third, and so on). Although the name of mathematical induction has “induction”, but mathematical induction is not a rigorous inductive reasoning method, it belongs to a completely rigorous deductive reasoning method. In fact, all mathematical proofs are deductive.

Natural numbers are the numbers that represent the number of objects, i.e. starting from 0, 0, 1, 2, 3, 4… One after another, to form an infinite collective, i.e., non-negative integers.

1.2 Deduction steps

After a simple understanding of the concept of mathematical induction, we will look at the deduction steps of mathematical induction.

We know that mathematical induction is used to prove that any given case is true, that is, the first case, the second case, all the way down.

The proof steps are as follows:

1. Prove whether the base case (usually N = 1) holds. The proof is true for N=1. We just have to start with the smallest natural numbers. This step is usually very simple. The key is to prove step two.

2. Prove that N > 1, assuming n-1, is true for N (N is any natural number greater than 1). So this is not a direct proof, but if we assume that N minus 1 is true, we can use this to say that N is true. This is true for all natural numbers. Because it’s true for 1, it’s true for 2, it’s true for 3. So that proves that this is true for all natural numbers. We’ll find mathematical induction very useful for proving things like arithmetic, ratio, and summation of squares and cubes.

1.3 small chestnut

Let’s take a little chestnut and review how we proved by induction in high school.

Example:

Proof: 1 + 2 + 3 +... +n = n(n+1)/2Copy the code

Let’s apply the above 1.2 deduction steps.

• Step 1: Prove the base case (usually N = 1).

So if we put N equals 1 on the left and the right, we get

1 = 1 * (1 + 1) / 2Copy the code

Set up!

• Step 2: Prove N > 1, assuming n-1 is true, then true for N (N is any natural number greater than 1).

There are two steps we need to take here.

• ① The hypothesis is true for n-1

We still contemporize n-1 into the left and right sides of the equal sign, so:

1 + 2 + 3 +... +(n-1) = (n-1)n/2Copy the code

• ② Substitute the hypothesis conclusion and add N

If we assume that n-1 is true, then if we add N to both the left and right sides of the equal sign, it must also be true, so that:

1 + 2 + 3... +(n-1)+n = (n-1)n/2+nCopy the code

If we simplify the right-hand side, we get n(n+1)/2, then our final proof is true!

That is: 1 + 2 + 3 +… Plus n is equal to n times n plus 1 over 2. Through the above steps, we can prove that this formula is true.

1.4 summary

Induction works when we want to solve a problem to solve its subproblems, and its subproblems become subproblems of the subproblems, and we find that these problems are actually a model, that is to say, there are the same logical induction treatment terms.

Now let’s look at how we write programs that relate to mathematical induction.

2. Recursively

Speaking of recursive algorithms, we’ve all heard or written about them. I remember the first contact with recursive algorithm, or the first year of learning the C language written by Tan Haoqiang teacher, which introduced the recursive algorithm. The impression I get is: call yourself. Later in my work, I didn’t use it much. I only used recursive algorithm once when I wrote the cascading menu. In this chapter, we’ll review the recursion algorithms we’ve learned by mathematical induction.

2.1 Understand recursion

The basic idea of recursion: and so on

To be specific, it is to transform large scale problems into small scale similar sub-problems to solve. In function implementation, because the way to solve a big problem is often the same as the way to solve a small problem, the situation arises when the function calls itself. In addition, the problem solving function must have an obvious end condition, so that it does not produce infinite recursion. If you look closely at recursion, you will find that the mathematical model of recursion is in fact induction.

2.2 Recursive conditions

There are some basic conditions that need to be met when we use recursion, and if they are not met, there is the possibility of infinite recursion, which eventually causes the stack to overflow.

Meet the conditions:

1. Strictly define recursive functions, including parameters, return values, and other variables.
2. First general case, then special case.
3. There are exit conditions. Conditions that allow recursion to exit normally.
4. Each call must reduce the size of the problem, and the new problem has the same form as the original problem, that is, a rule.

The above conditions can also be reduced to two main conditions: regularity and exit conditions. Let’s combine the above conditions with the case to understand.

2.3 small chestnut

2.3.1 Recursive summation

Examples:

1 + 2 + 3 +... +n=?Copy the code

Step 1: Strictly define recursive functions, including parameters, return values, and other variables.

From our first glance, we can see that this is a simple sum, starting with 1:1+2+3+… All the way to n. So we can define a method with n as an entry and int as a return type. We call it recursionSum.

Public static int recursionSum(int n)return 0;
}

System.out.println("公众号：Coder编程：" + recursionSum(0));

Copy the code

So we’re done with the first step.

Step 2: General case first, then special case.

So let’s start with the general case, like 1,2,3, and so on. That is:

public static int recursionSum(int n) { 
    if(n == 1) {
        return 1;
    }
    
    if(n == 2) {
        return1 + 2; }if(n == 3) {
        return1 + 2 + 3; }return 0;
}

System.out.println("公众号：Coder编程：" + recursionSum(3));

Copy the code

Step 3: Have exit conditions. Conditions that allow recursion to exit normally.

In fact, when we finish the second step, we will find that we have finished the third step. I have the condition for the recursion to exit properly!

Step 4: Each call must reduce the size of the problem, and the new problem has the same form as the original problem, namely the rule.

This step is the most critical, but also the most core! We need to find patterns and reduce the scale of the problem. And what we find is that when we want the sum of the NTH number, we have to know the sum of the first n-1 number, which is sum of n-1. The sum of the first N numbers is sum(n-1)+N. Once we have found this pattern, we can define a temporary variable sum to accept the sum of the first N numbers.

public static int recursionSum(int n) {

    if(n == 1) {
        return 1;
    }
    
    if(n == 2) {
        return1 + 2; }if(n == 3) {
        return1 + 2 + 3; } int sum = recursionSum(n-1)+n;return sum;
}

System.out.println(Coder programming: Sum of the first 5 numbers + recursionSum(5));

Copy the code

The output is 15

Let’s optimize:

public static int recursionSum(int n) {

    if (n < 0){
       throw new Exception("Parameters cannot be negative!");
    }
    if(n == 1) {
        return 1;
    }
    
    return recursionSum(n-1)+n;
}

System.out.println(Coder programming: Sum of the first 5 numbers + recursionSum(5));

Copy the code

Did you suddenly realize that recursion isn’t as hard as you thought?

2.3.2 What do we learn from others?

Next we upgrade the difficulty level! Let’s see if everyone understands this. I won’t be as verbose as the sum above!

2.3.2.1 o factorial

Example: Find n factorial (n>1, n is a positive integer)

The factorial formula is: factorial(n)=n*factorial(n-1), where n is a non-negative integer and 0! = 1, 1! =1 so I’m not going to go into too much detail here, but it’s the same thing as the sum, and you can try to write it yourself, and I’ll just paste the code:

public static int factorial(int n) throws Exception {
    if (n < 0){
        throw new Exception("Parameters cannot be negative!");
    }else if (n == 1 || n == 0) {
        return 1;
    }else {
        return n * factorial(n - 1);
    }
}

System.out.println(Coder programming: 3 factorial: + factorial(3));


Copy the code

Coder: 3 factorial :6

2.3.2.2 Fibonacci sequence

I think you’re familiar with the Fibonacci sequence, but let’s go back and see what the Fibonacci sequence is.

Fibonacci sequence: 1, 1, 2, 3, 5, 8, 13, 21…..

You can see from the third: the third term is equal to the sum of the first two terms. To summarize the recursive formula: :Fib(n)=Fib(n-1)+Fib(n-2). So we can use the first two as conditions to get out of recursion. If (n==1) retrun 1 if(n==2) return 1

So we can write programming code directly using formulas (rules) and exit conditions:

public static int fib(int n) throws Exception {
    if (n < 0) {
        throw new Exception("Parameters cannot be negative!");
    }else if (n == 0 || n == 1){
        return n;
    }else {
        return fib(n - 1) + fib(n - 2);
    }
}

System.out.println(Coder programming: Fibonacci sequence: + fib(3));

Copy the code

2.3.2.3 Hannotta problem

Legend has it that in ancient Indian temples, there was a game called Hanoi. This game is on A copper plate device, there are three rods (numbered A, B and C), in the bottom of A rod, from the largest to the smallest in order to place different number of gold discs (as shown below).

The goal of the game: move all the gold disks on rod A to rod C, and still keep the original order of stacking.

Operation rule: only one plate can be moved at A time, and in the process of moving, the big plate should always be kept on the bottom of the three rods, and the small plate should always be on the top. The plate can be placed on any of the rods A, B and C during the operation.

Before we summarize the rules and write the code, let’s play a few simple (first general, then specific) :

Note: We used the size of the number as the size of the plate.

1. The case of a plate:

   1.1 Move tray no.1 of pillar A directly to pillar C. 1.2 the end.

2. Two plates:

   2.1 Move tray no.1 from pillar A to pillar B. 2.2 Move plate no.2 from pillar A to pillar C. 2.3 Move tray no. 1 from pillar B to pillar C. 2.4 the end.

3. Three plates:

   3.1 Move tray no.1 from pillar A to pillar C. 3.2 Move plate no.2 from pillar A to pillar B. 3.3 Move tray no. 1 from pillar C to pillar B. 3.4 Move tray No.3 from pillar A to pillar C. 3.5 Move tray no. 1 from pillar B to pillar A. 3.6 Move plate no. 2 from pillar B to pillar C. 3.7 Move tray 1 from pillar A to pillar C. 3.8 the end.

---

We’ll see that as the number of plates increases, it becomes harder to move them.

Now don’t be afraid, let’s go back to the problem: when the number of plates is 4, 5… So at N, what do we do? Can we solve it by mathematical induction or by recursion? The answer is: yes. At this point we need to find out where is their pattern?

Now let’s look at what happens to the plates up here in general?

• 1. When there is only one plate, move the plate directly to the target pillar C. namelyExit criteria.
• 2. When there are only two plates, we only need to take pillar B as the intermediary, put plate 1 on the intermediary pillar B, then put plate 2 on the target pillar C, and finally put the plate on the intermediary pillar B on the target pillar C.

The second point can be viewed as: when we have N plates, the NTH plate is a plate, and (n-1) plates are a plate. It is necessary to place (n-1) plates on the intermediate pillar B and N plates on the target pillar C. The law.

When we have three plates, we find a problem: character change

1. Consider the (n-1)~1 plates of tower A as A plate and place them on the middle pillar B, then place the NTH plate on the target pillar C. Now pillar A is empty! Pillar A becomes the intermediate pillar and pillar B becomes the initial pillar.

2. Pillar B has n-1 plates at this time, regard the (n-2)~1 plates as A plate and place them on the intermediate pillar A, and then place the (n-1) plate of pillar B on the target pillar C. Now pillar B is empty! Pillar B becomes the intermediate pillar, and pillar A becomes the starting pillar!

Repeat steps 1 and 2 until all plates are on target tower C.

To sum up:

1. Move n-1 plates from the initial pillar A to the intermediate pillar B.
2. Place the remaining plate (the largest plate) from the initial pillar A on the target pillar C.
3. Move N -1 plates on intermediate pillar B to target pillar C.

move(3,"A"."B"."C"); /** * @param dish * @param from initial column * @param temp intermediate column * @param to target column */ public static void move(int dish,String from,String temp,String to){if(dish == 1){
        System.out.println("Turn the plate"+dish+"From the Pillar"+from+"Move to target post"+to);
    }else{ move(dish-1,from,to,temp); //A is the initial column, B is the target column, and C is the intermediate column."Turn the plate"+dish+"From the Pillar"+from+"Move to target post"+to); move(dish-1,temp,from,to); //B is the initial column, C is the target column, A is the intermediate column}}Copy the code

• move(dish-1,from,to,temp); //A is the initial pillar, B is the target pillar, and C is the intermediate pillar.

• move(dish-1,temp,from,to); //B is the initial pillar, C is the target pillar, and A is the intermediate pillar. Place the previous N -1 plates into the C target pillar.

Print result:

At the end of the article

This chapter mainly introduces some ideas of mathematical induction and recursive algorithm. Hope to help you! In the future, I will add a little positive energy for each chapter at the beginning of each article, and five programming related English words at the end of the article to learn Some English. I hope everyone can be positive like me every day, learning and progress together!

Learn some English

• JRE Java Runtime Environment (JRE), a collection of environments necessary to run Java programs, including the JVM standard implementation and Java core class libraries.
• JSDK Java Software Development Kit, equivalent to JDK and J2SE.
• JDK Java Development Kit(Java Development Kit): includes the runtime environment, compilation tools and other tools, source code, etc., basically equivalent to J2SE.
• The J2ME Java 2 Micro Edition (JAVA2 Lite) API specification is based on J2SE, but has been modified to fit the single requirements of a particular product. J2ME enables JAVA programs to be easily applied to small devices such as phone cards and pagers. It includes two types of components, namely configuration and profile.

Welcome to pay attention to the public number: Coder programming to obtain the latest original technical articles and related free learning materials, anytime, anywhere to learn technical knowledge!

Reference article:

www.cnblogs.com/ysocean/p/8…

www.nowamagic.net/librarys/ve…

Recommended reading

A guide to understand the TCP “sliding window” protocol

Learn how to use a JOIN in a database

To understand “packing and unpacking”