《函数递归（ function recursion）.doc》由会员分享，可在线阅读，更多相关《函数递归（ function recursion）.doc（11页珍藏版）》请在金锄头文库上搜索。
1、713 函数递归（713 function recursion）It is a wise man, there must be a loss; a fool, there will be one. Energy-saving, no one is known to litchi. The bridge is still in the energy-saving, energy-saving. The mighty river flows eastward. waves are truly great men through the ages. The two sides of Castle P
2、eak relative, from a day to. First, stackWhen it comes to recursive functions, by the way, the concept of the stack.Stack is a backward in first out (push) and pop (POP) data structure. When the program is running, the system enters an object into the stack each time, and then the stack pointer move
3、s down a position. When the system pops up an object from the stack, the object that has recently entered the stack will pop up. Then the stack pointer moves up a position. Programmers often use the stack data structure to handle programming problems that are best suited to the description of backwa
4、rd first out logic. The stack in the program discussed here is present in every program. It does not require programmers to write code to maintain, but runs automatically by the system. The so-called system automatic maintenance, in fact, is generated by the compiler code. Even if you dont see them
5、in the source code, programmers should know something about it.Look at how the stack in the program works. When a function (caller) calls another function (callee), the runtime system will give the caller all the arguments and the return address onto the stack, the stack pointer will move to the rig
6、ht position to accommodate these data. The last entry to the stack is the callers return address. When the caller starts executing, the system presses the callers independent variable into the stack and moves the stack pointer down to ensure that there is enough space to store all the arguments decl
7、ared by the caller. When the caller presses the argument into the stack, the caller builds the parameter in the form of an independent variable in the stack. Other variables inside the caller are also stored in the stack. Because of these stack operations, the stack pointer has moved below all these
8、 local variables. However, the caller records the initial stack pointer when it is beginning to execute, and uses him as a reference to access the variables in the stack with positive or negative offset values. When the caller is ready to return, the system pops up all the independent variables in t
9、he stack, and then the stack pointer moves the position where the caller just started. Then the caller returns, and the system pops back the address from the stack, and the caller can continue to execute it. When the caller continues to execute, the system pops up the callers arguments from the stac
10、k, so the stack pointer returns to the location before the call occurs.Maybe the beginning of the study can not understand the above, the stack refers to the pointer problem, you can see some specific data structure books. If you want to learn programming language, data structure is bound to learn.T
11、wo, recursionRecursion is a very important part of function realization, and many programs use recursive function more or less. Recursion means that the function calls itself itself, or calls itself in the lower function of its own function call.Recursion is implemented because each execution of a f
12、unction has its own parameters and copies of local variables in the stack, which are irrelevant to the other execution of the function. This mechanism is the basis for most modern programming languages to implement subroutine structures, and makes recursion possible. Suppose a call function calls a
13、call function, and then the invoked function calls the calling function in turn. These second calls are called recursive functions because they occur before the current execution of the calling function is finished. Moreover, because the original call function, now called functions on the stack in t
14、he lower position has its independent set of parameters and variables, parameters and variables of the original will not be affected, so the recursion can work normally. The procedure of traversing the execution of these functions is called recursive descent.Programmers need to ensure that recursive
15、 functions do not arbitrarily change the values of static and global variables in order to avoid errors in the upper level functions during recursive descent. The programmer must also ensure that there is a termination condition to end the recursive descent process,And go back to the top floor.For e
16、xample, a program like this is recursion:Void a (int);(main)Int num=5;A (Num);Void a (int Num)If (num=0) return;Printf (%d, num);A (-num);In the function a (), it calls itself, that is, its own call itself, so that is recursive. So some people might want to think, isnt this a dead cycle? So in recursive function, must have return statement, no return statement recursive function is dead cycle
