The ingenious understanding of recursive thought

Logic is the age of mathematics , Mathematics is the age of logic .

—— Russell

“ Recursion ”

This is in the program 、 The foundation and top priority in algorithm design . It took me a lot of time to understand this , For beginners , How to show a process vividly , Became the key to understanding this idea .

The reason for this blog post , From a question my classmate asked me ：

I'll see it , This wave , This wave is obviously going back ！！

I thought , How to explain , Is to open Baidu search to return ：

Define

The programming technique of calling itself is called recursion （ recursion）. Recursion as an algorithm is widely used in programming languages . A procedure or function has a way of calling itself directly or indirectly in its definition or description , It usually transforms a large and complex problem into a smaller problem similar to the original problem to solve , The recursive strategy only needs a few programs to describe the repeated calculation needed in the process of solving problems , It greatly reduces the amount of code in the program . Recursion is the ability to define an infinite set of objects with finite statements . In general , Recursion requires boundary conditions 、 Step forward and step back . When the boundary conditions are not satisfied , Go back and forth ; When the boundary conditions are satisfied , To return to .

I think this , That's such a tough explanation , Let's not bother people , So this explanation has been pigeon for several days

ideas

One night of fish fishing , I suddenly came up with a vivid example of interpretation recursion , That's it ：

Russian Dolls ！！

So , How to use the idea of Russian dolls to understand the idea of recursion ？

And it's known to all , Recursion is actually a program calling itself , It's not like , I have a self in my stomach ？

But , The way we open this set of Dolls , You have to follow the following rules ;

Take the top half of the dolls first （ The code above the function that executes the call itself ）;

Keep taking the upper half , Until I took out a baby that couldn't be opened （ Go back to the end ）;

Look at this baby who can't have a baby again （ Complete execution of this most “ deep ” Function of ）;

Take out the lower body of all dolls in turn （ Execute the bottom half of all recursive functions from the bottom up ）.

Case interpretation

Let's take a look at the code to find the depth of the tree ：

int TreeDepth(BT *T){
    int ld=0,rd=0;
    if(T==NULL) return 0;
    else{
        ld=TreeDepth(T->lchild);
        rd=TreeDepth(T->rchild);
        if(ld>rd)
            return ld+1;
        else
            return rd+1;
    }
}

I'll draw a picture and see

Suppose there is such a tree ,BT Is the index in the function *T The position of

We run this code

int TreeDepth(BT *T){
    int ld=0,rd=0;
    if(T==NULL) return 0;
    else{
        ld=TreeDepth(T->lchild);

First, return to the bottom , Walking down , Is full of NULL 了 , You can run the next section of code

if(ld>rd)
            return ld+1;
        else
            return rd+1;

Of course , Here ld and rd All are 0, The return value is 1, According to

ld=TreeDepth(T->lchild);

And the last level of function ld=1

Let's continue to see , Because the execution of this function has ended , Let's run the second half of the code from the previous function .

       rd=TreeDepth(T->rchild);
        if(ld>rd)
            return ld+1;
        else
            return rd+1;
    }
}

Here we find , You can go all the way down the right tree , Refer to the previous step , And so on , We get the following figure

And push on , The return value of the whole program is clear at a glance

I'd like to talk about depth first search again （DFS）, As we all know, the most basic skill of deep search is recursion .

PS： Although deep search can also be achieved by stack , But recursion means that the program calls up the stack to store data , There is little difference .

Trees are special graphs , The traversal of the tree is also the graph traversal , This way of traversing the depth in one breath , It's what we call DFS, In the process of learning the foundation of tree , We can also experience many properties of graphs

I hope that my proposal can cause more thinking