Disclaimer: This article is the author of the study SICP abstract knowledge about the process of understanding, due to the book's statements somewhat obscure, it will be understood that the author wants to help everyone to share some of my friends. The original book for tail recursion and not much introduction, but here is a detailed explanation.
It is now 1:48. Ah, just to finish this log. Could not help but want to say something, perhaps when a bad book Torr. These may be for many people, is of no use, they may even despise what I write, that takes time for these things are not worth it. For these people, I would say that every person has a keen interest in computers, have a wish to understand thoroughly enough in the face of more than 12 hours per day is the desire of this machine works. Like SICP and CSAPP this book certainly is boring, you might see the day, carefully read what words can only see thirty-four, but how can you really understand the meaning of these few pages of the book, then the harvest will be great. Since last May, I recommend reading CSAPP Master Chen, I really found that looks very boring, but to let them go read a book. Such books are difficult to read, if you take a strong utilitarian to read it, it is impossible to read on the. I thought to support the day I sat there pondering these pages in the book, said the core meaning of the power is derived from what I really want to know is how to work a computer, access to such information for me is very happy this feeling is wonderful.
Calculate the difference between functions and procedures
Function is generally a form of computing science index above, tend to explain the statement, describe how a given one or several parameters to calculate a value. SICP as a function of the square root of a number of requirements, we are in the description of the function can be inferred some specific properties and general facts about the square root, but we can not calculate the square root of a number of specific methods learned. You might say, is not the square root square root it. But you have not thought of, [square root] is only an illustrative statement, specifically how to calculate you still do not know. It extends to a computer which functions, in fact, function and significance of mathematics above is the same, we just replaced high-level programming language to write us a description of the general function of the fact that, in fact, we did not give a specific calculation process. Such as square root, if we are to call math.h library functions to find the words: sqrt (x * 1.0), this form is only a declarative statement, we use this statement to direct a computer to calculate, but in fact this function does not provide a specific calculation. Among computer interpreter is responsible for the explanatory statement of this into real calculations (when looking to write an interpreter wow).
In fact, I feel this difference between the two is the same and writing, one outline, the other is the specific content.
Abstract touch process
SICP request regarding a number of the square root of the problem, using Newton's law of successive approximation, continued to novelty guess, until the results meet certain end precision. The square root function is a large, want to complete this great feature also requires some small features to assist.
Abstract process is the essence of a functional decomposition
We put a big whole calculation process is divided into several parts, each part of which can be individually complete a small feature, but they combined to complete the final function. Abstract and C ++ in the process of so-called object-oriented thinking is similar and, chances are one thing, I'm not sure, but the process of abstraction that is a meaning, that is, it is important that the creators of the implementation process , and for the user, the process of abstraction can be masked internal implementation details, thereby reducing the burden on the user, only care about what the process of "black box" can do. Therefore, such an action would increase the local alternative program, since the achievement of a function, it can achieve a variety of internal processes.
Abstract 1- local name
We all know that when the calling function or process, sometimes need to pass some of the appropriate parameters in the procedure call in the form of a function name of the parameter is not important for us, with respect to the user is indeed so . But for the designer process, the names of formal parameters, or the names of local variables for the entire process to normal execution is very important. This is also a process of abstraction among the details of the computer package to something more complicated like the interior.
About the process of abstraction may have two new concepts, bound variables and free variables. On a single process is concerned, I understand that is a kind of bound variables does not matter what the name is, but one way variance procedure does not change the meaning of the name change after reunification, he has his own scope, analogous to local variables it. The free variables analogous to global variables or static variables, so I understand. Bound variable name is not important, what is important is to place a constraint with the same variable.
Why the name constraint variables for the implementation process is very important to do. A very direct understanding is: local variables can shield the global variable with the same name in scope, an analogy, bound variables in the appropriate scope will shield the free variables of the same name.
(Define (good-enough? Guess x)
((Abs (- (square guess) x)) 0.001))
For example in terms of the above process, guess and x is a good-enough two bound variables of the process, < , abs, -?, Square is a free variable. And free variables are related to the environment, they have to determine the significance of maintaining their normal execution, but if we guess the bound variables renamed abs, abs significance of this will lead to free variables are bound variables shield occurred during the abs is bound variables, not having free variables among the absolute value function.
So, for designers in terms of process, the process of achieving the free variables and bound variables names are used is important to note a place where, the successful implementation of a process depends on the names of bound variables and free variables different and meaning free variable correctly.
Abstract definition and internal block structure 2-
This is the more abstract process for the user of our considerations, it is also a topical concepts such as local variables, only internal scope can access and identify him, it is not known outside the scope of this thing scope of. Just before we abstract is variable, this is the process of abstraction.
sicp the square root of the process, and user interaction is just an interface sqrt, wherein the specific implementation details of the sub-processes are one of the abstract [black box]. But for users, these implementations black box calculation process is of no use, it will only disrupt their thinking, and users want to customize a time with these black boxes of the same name in one process is not allowed (not in a defined scope of the two processes of the same name), which has a particular function [black box] pollutes the global namespace environment.
For a partial structure of things, we better way is to define them within this structure should not be placed within the scope of the global environment, because you need not other people's needs, if other people do not need them something, then their name is likely to cause naming conflicts procedure calls, resulting in procedural confusion.
scheme to support the process of internal re-define a new process, a new definition of internal processes within the scope only visible, external definitions are not aware of these processes inside.
(Define (sqrt x)
(Define (good-enough? Guess x)
(Abs (- (square guess) x)) 0.001))
(Define (improve guess x)
(Average guess (/ x guess)))
(Define (sqrt-iter guess x)
(If (good-enough? Guess x) guess
(Sqrt-iter (improve guess x) x)))
(Sqrt-iter 1.0 x))
According to the above example, we put the square root of this calculation process used in a small black box a are defined in this internal process, they do not see the outside of the process, this nested procedure definition called a block structure. Localized make procedures clearer, to reduce global names, to reduce mutual interference. In addition, since some of the black box after conducted internally defined, there is a place for improvement is the use of the parameter x. Since the local process parameters are within the scope of x, we do not have to re-transfer process in the local x, and can be called directly. With respect to the local process, now from the original X-bound variables, now becomes a free variable.
Multiple shape calculation process
We can use different types of the same procedure to complete a task, then the real time programming, we should use what way? According to the angle before the data structure point of view, we have two indicators: time complexity and space complexity. Different processes naturally have different computational procedures that we should measure the two indicators by the above-mentioned two different calculation process to determine the final choice of which as a final version. This requires us to be able to accurately observe the process of any one of the execution and implementation of the results, as well as a variety of resources to implement the process of consuming.
Recursion and iteration should be two very important computing form. If a problem can simultaneously use two forms to solve this, then we should choose which one do?
In the examples to illustrate the differences between recursive and iterative before, we must first clear distinction between this two concepts:
Recursive calculation process: the case of the calculation and implementation of specific acts reflect the calculation takes some of the information and the availability of resources to maintain the process of implementation. Recursively defined process: the program is written, the code defines the process appeared a call to the process itself, but the actual calculation may not need to spend resources to maintain the implementation process.
If there is now a demand n factorial needs: we have forward and reverse two approaches to obtain results
Reverse (linear recursion)
Algorithm is as follows:! N = n (n-1) = n (n-1) (n-2) ... ..2 1 = n * (n-1)!!!
With specific calculation process, we can write it to a process
(Define (factorial n)
(If (= n 1)
(* N (factorial (- n 1)))))
PS: This process can be seen at the time to call their own definition
Suppose now that we want to calculate (factorial 6), according to shceme substitution model is derived:
When we calculate (factorial 6) when, according to the definition of the calculation process to be executed (* 6 (factorial (- 6 1))). Through this a complex expression we can see, (factorial 6) The results of this step is not calculated, it is necessary to calculate the next state to assist it draw (factorial 6) The results of this step. Because this calculation is not completed to carry out other operations to assist complete, even if this operation is interrupted, since the break, and we need to preserve the scene, save the current state of the calculation (variables, and so some of the resources ) in order to smooth out immediately after the result of the convergence of computing on a state to calculate the final result. After the calculation process remains in this form until it encounters the boundary.
So far, we know, this calculation process is to calculate a delivery process, because he takes the process of computing resources in which to save some facts and information required. Recursive calculation process, surely we are all familiar with, it is a kind of delayed evaluation approach, the end result can not be obtained immediately, every time calculations are dependent on its calculation of the sub-state, until it encounters the border only after layer by layer returns the results, eventually returned to the starting point, the results obtained. It can be said, from the recursive procedure after pushing forward, calculating the final step, which is the final result, we might need to countdown the result of step, then the reciprocal of the first step, and so on, until the calculated to the first step when using the title of conditionality can be the first step in the final result, and then return to the starting point of the calculation results step by step, the final step is to calculate the location of the final result. (Depth-first search of truth) but too many times if calculated, iterative deep layers, leaving the process stack space is likely to overflow, causing the explosion stack.
Well, according to the above time and space complexity of the two targets, we will judge the recursive calculation process to calculate the factorial of good or bad. (In fact, the calculation process is the algorithm, a wood there?!)
We can see that if n is 6, then to calculate the total of 12 times, so if n is 5 to 10 times calculated, the corresponding time complexity can be roughly estimated as O (N). From (factorial 6) recursively to the border of the most low-end, when conducted a total of 6 iterations, as n increases, the number of recursive vary with n linear growth, the required memory space will be linear growth. So the complexity of the controls should be O (N).
In summary, the entire evaluation process has been completed recursive calculation, accurate to say that this is a linear recursive calculation process.
Forward (linear iteration)
Algorithm:! N is 1 from the beginning has been to take the tired n, the final result is equal multiplies n!
According to this algorithm, a write process is as follows
(Define (factorial n)
(Fact-iter 1 1 n))
(Define (fact-iter product counter max-count)
(If (counter max-count) product
(Fact-iter (* counter product) (+ counter 1)
From the above process, we can see that it is defined at the time, but also calls itself.
Every calculation state maintained by three variables, and the calculation of each state of computing and other states are independent, the results of each state does not depend on other states. Every state of the computation are crisp execution, the next state of computing resources required by an argument, after the previous calculation completion state of no use, and it does not have to hold anything useful to a state before or after a information, information needs are based on the parameters passed to the new state. Moreover, in the process of constant calculation, since the value of the information required has been passed as a parameter, once obtained the final result, do not like recursion, the calculation results are returned to the previous state, but directly returned to a caller began. The calling process is to open up space in the stack memory, according to the characteristics of the above calculation, the stack space before a state can be destroyed immediately after the end of the calculations used to avoid stack overflow.
Such a calculation process, it is easy to see, the time complexity of O (N), space complexity, because you need to save each calculation only three variables, it does not change with n varies, for the O (1), constant level. This calculation process is not just this, the computer space complexity among all calculations should be completed at a constant level, because the memory space is limited.
The above calculation process is called iteration, if alone this instance, it should be a linear iterative process.
The difference between iteration and recursion
In the iterative process, the information required to calculate each state are stored in several variables, to preserve some implicit message passed as an argument in the past, it does not require additional stack space to open up again. But recursion is needed, there is the danger of stack overflow.
In the iterative process, if we lost some states, you can start from any state to continue the calculation, because the information required for the calculation are stored in several variables, even if only one state in the middle, we can according to the calculation process all the lost state all worked out. But if it is recursive, and if information on a state of lost, even if it's sub-state calculated the results are returned to it, because the state lost some necessary information so that the calculation process can not go on.
Although both are in the process of defining the time of the call itself, but it is clear that the definition of an iterative process belongs to recursively define the process. Recursive recursive calculation process belongs.
The ultimate esoteric black magic: tail recursion
General programming language through some complex structures to describe the circulation of iterations, but it can be used in the scheme in the form of recursive described iteration.
Observation of the above two factorial process, we can see. Although both calls itself recursively with the form to define the entire process, all belong to the upper surface of recursive calls, however, "recursive" version, after the final recursive call, also need to be considered by n operations as is the completion of the calculation, but in [iterations] versions, calling the recursive method belongs to the last one, at the end of recursive calls executed, the calculation will execute over, the last part of the operation of the process, which is "tail recursion." Tail recursion recursive relative to normal, its recursive call is the last process before the process of calculating the accumulated information has no effect on the final results of the next recursive call, then this procedure call information stored in the stack you can be completely removed. The recursive process space left after use. So, this means that if you use tail-recursive manner, it can achieve an infinite recursion.
Tail-recursive nature, in fact, is "all states" recursive method required by the process of the argument to the next call. The last time such a call will not have to save some additional information, and to calculate the boundaries of time, because the result of the calculation has been accumulated, the final result of the calculation to the end, when it obtained, can be returned directly to the most I began to call the caller of this method.
As to normal recursion into tail-recursive method, I think the more direct approach is that recursion is considered normal from back to front, if you write tail recursion, then put back to consider the issue in the past, and the required information as parameters transfer.
In general, although the process definition, it appears to be recursive, but the principle is the actual calculation process may be iterative, there may be recursive, because the calculation is iterative tail recursion can be used to define.