Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

preface

In programming, recursion is certainly familiar to you, and today we are going to summarize something about recursion.

What? ! You are strange, to brush the topic, after you are familiar.

Definition of recursion

The technique by which a program calls itself is called recursion

What does recursion look like

The first thing that comes to mind when we think about examples is factorials.

n! = n * (n-1) * (n-2) * … * 1(n>0)

5! Is equal to 5 times 4 times 3 times 2 times 1

Factorial is we from the primary school mathematics contact things, did not expect it is still with us 🙄

Implement it in code:

function recursion(n) {
    if (n == 1) return n
    return n * recursion(n - 1)}console.log(recursion(5)) // 5 * 4 * 3 * 2 * 1 = 120
Copy the code

Let’s take another example, the famous Hanoi Tower problem, which is also in our middle and high school textbooks:

This problem is also solved recursively:

function hanoi( n, p1, p2, p3)
{
	if(1 == n)
		
		console.log('Plate from' + p1 + 'Move to' + p3);
	else
	{
		hanoi(n-1, p1, p3, p2);
		console.log('Plate from' + p1 + 'Move to' + p3);
		hanoi(n-1, p2, p1, p3);
	}
}
hanoi(3.'p1'.'p2'.'p3');
Copy the code

Conclusion the ha

Now that want to write a recursive, will know that it have what condition, it is not hard to see from the above example, recursion is a boundary condition, the factorial n = = 1 and 1 = = n Hanoi tower are boundary conditions, the recursion has two parts, the boundary condition is met when in the process of return, boundary conditions are not satisfied, again into the recursive process.

So what else does it have?

  • It has to have an exit condition, that is, it has to end at a point where it becomes non-recursive.
  • The recursive subproblem is the same as the original problem and gradually becomes simpler.

To sum up: we write recursion with boundary conditions and a two-part process based on the boundary conditions.

And the idea of using recursion is to gradually simplify the problem and end up with a non-recursive solution.

The last

Recursion, I think, is a solution to a problem after thinking about it.

You already know what the boundary conditions are when you come up with a recursive solution, just write the recursive part, and then use a non-recursive exit.

Point a favor, learning progress together bar