Difference between backtracking and recursion

Look at the data structure recently , It is found that many recursion and backtracking problems are used , I really don't know the difference between the two , I checked some information recently , Let's summarize .

In order to describe a certain state of the problem , The previous state of this state must be used , And describe the previous state , You must use the previous state of the previous state …… This method of defining yourself by yourself , Called recursive definition . In the form of f(n) = n*f(n-1), if n=0,f(n)=1.

Starting from one possibility of the problem , Search for all the possibilities that can be achieved from this situation , When this road comes to ” At the end of “ When , Go back to the starting point , From another possibility , Continue to search . This continuous ” to flash back “ The way to find the solution , Referred to as ” backtracking “.

Recursion is an algorithm structure , Recursion will appear in the subroutine, calling itself or indirectly calling itself . The most direct recursive application is to calculate the factorial of continuous numbers , The law of calculation ：n!=(n-1)!*n.
Observe the law of factorial calculation , The result of the former number formation can be directly applied to the calculation of the latter number formation .

int fac（int n）
if（n==1）
return n;
else
return n*fac(n-1);

Backtracking is an algorithmic idea , It can be implemented recursively . Generally speaking, backtracking is a kind of Temptation , Similar to exhaustive , But backtracking has “ prune ” function , For example, the summation problem . Given 7 A digital ,1 2 3 4 5 6 7 Sum equals 7 The combination of , Search from small to large , choice 1+2+3+4 =10>7, Already exceeded 7, After that 5 6 7 There's no need to continue , This is an optimization of the search process . If there is anything unclear, you can have a look 8 queens problem .

Link to the original text ：https://blog.csdn.net/u014772862/article/details/51789015