26 I.Preliminaries would represent "while"loops or conditional statements.Thus,this abuse of the medium of flowcharts has also caused many researchers to recommend that they be used with caution.Another concern is the fact that many kinds of algorithms simply do not lend themselves naturally to graphical,diagrammatic rendition offered by the likes of flowcharts.The resulting artifacts will often be spaghetti-like,decreasing. rather than increasing,a viewer's ability to understand what is really going on. The above discussion notwithstanding,we shall see in Chapter 14 that there are diagrammatic languages (we shall call them visual formalisms)that are very successful,mainly in the context of specifying the behavior of large and complex systems.The problem there is not describing computations,as algorithms do,but specifying reactive and interactive behavior over time. Subroutines,or Procedures Suppose we are given a lengthy text and we are interested in finding out how avaricious its author is by counting the number of sentences that contain the word "money."In such instances,we are not interested in the number of times the word "money"occurs,but in the number of sentences in which it occurs.An algorithm can be designed to run through the text looking for"money."Upon finding such an occurrence,it proceeds to run ahead looking for the end of a sentence,which for our purposes is assumed to be a period followed by a space;that is,the"."combination. When the end of a sentence is found,the algorithm adds 1 to a counter (that is,a "noted number,"as in the salary summation algorithm),which was initialized to 0 at the start.It then resumes its search for"money"from the beginning of the next sentence;that is,from the letter following the combination.Of course,the algorithm must keep looking out for the end of the text,so that it can output the value of the counter when it is reached. The algorithm takes the form of an external loop whose duty it is to count the relevant sentences.Within this loop there are two searches,one for "money"and one for the"."combination,each constituting a loop in itself(see the schematic flowchart of Figure 2.5).The point is that the two internal loops are very similar;in fact,they both do exactly the same thing-they search for a sequence of symbols in a text.Having both loops appear explicitly in the algorithm clearly works,but we can do better. The idea is to write the searching loop only once,with a parameter that is assumed to contain the particular combination of symbols searched for.This algorithmic segment is called a subroutine or a procedure and it is activated (or invoked,or called)twice in the main algorithm,once with"money"as its parameter, and once with the"."combination.The text of the subroutine is provided separately, and it refers to the varying parameter by a name,say X.The subroutine assumes that we are pointing to some place in the input text,and it might look as follows: subroutine search-for X: (1)do the following until either the combination X is being pointed at,or the end of the text is reached: (1.1)advance the pointer one symbol in the text;
P1: GIG PE002-02drv PE002-Harel PE002-Harel-v4.cls March 18, 2004 13:47 26 I. Preliminaries would represent “while” loops or conditional statements. Thus, this abuse of the medium of flowcharts has also caused many researchers to recommend that they be used with caution. Another concern is the fact that many kinds of algorithms simply do not lend themselves naturally to graphical, diagrammatic rendition offered by the likes of flowcharts. The resulting artifacts will often be spaghetti-like, decreasing, rather than increasing, a viewer’s ability to understand what is really going on. The above discussion notwithstanding, we shall see in Chapter 14 that there are diagrammatic languages (we shall call them visual formalisms) that are very successful, mainly in the context of specifying the behavior of large and complex systems. The problem there is not describing computations, as algorithms do, but specifying reactive and interactive behavior over time. ■ ■ ■ Subroutines, or Procedures Suppose we are given a lengthy text and we are interested in finding out how avaricious its author is by counting the number of sentences that contain the word “money.” In such instances, we are not interested in the number of times the word “money” occurs, but in the number of sentences in which it occurs. An algorithm can be designed to run through the text looking for “money.” Upon finding such an occurrence, it proceeds to run ahead looking for the end of a sentence, which for our purposes is assumed to be a period followed by a space; that is, the “. ” combination. When the end of a sentence is found, the algorithm adds 1 to a counter (that is, a “noted number,” as in the salary summation algorithm), which was initialized to 0 at the start. It then resumes its search for “money” from the beginning of the next sentence; that is, from the letter following the combination. Of course, the algorithm must keep looking out for the end of the text, so that it can output the value of the counter when it is reached. The algorithm takes the form of an external loop whose duty it is to count the relevant sentences. Within this loop there are two searches, one for “money” and one for the “. ” combination, each constituting a loop in itself (see the schematic flowchart of Figure 2.5). The point is that the two internal loops are very similar; in fact, they both do exactly the same thing—they search for a sequence of symbols in a text. Having both loops appear explicitly in the algorithm clearly works, but we can do better. The idea is to write the searching loop only once, with a parameter that is assumed to contain the particular combination of symbols searched for. This algorithmic segment is called a subroutine or a procedure and it is activated (or invoked, or called) twice in the main algorithm, once with “money” as its parameter, and once with the “. ” combination. The text of the subroutine is provided separately, and it refers to the varying parameter by a name, say X. The subroutine assumes that we are pointing to some place in the input text, and it might look as follows: subroutine search-for X: (1) do the following until either the combination X is being pointed at, or the end of the text is reached: (1.1) advance the pointer one symbol in the text;
2.Algorithms and Data 27 (2)if the end of the text is reached,output the counter's value and stop; (3)otherwise return to the main algorithm. The main part of the algorithm will utilize the search subroutine twice,by instructions of the form“call search-for‘money'”and“call search-for‘.'”Contrast Figure2.5 with Figure 2.6,in which the version with the subroutine is shown schematically. The processor that runs around doing things will now have to be slightly more sophisticated.When told to "call"a subroutine,it will stop whatever it has been doing,remember where it was,pick up the parameter(s),so to speak,and move Figure 2.5 start Schematic flowchart for sentences with “money." initialize counter and pointer check next INSIDE few symbols TEXT Searching for“money” found NO advance pointer "money”? (including check for end of text) YES END OF TEXT output counter P stop check next INSIDE few symbols TEXT Searching advance pointer for end of found No (including check sentence 1 for end of text) YES END OF TEXT output counter stop increase counter
P1: GIG PE002-02drv PE002-Harel PE002-Harel-v4.cls March 18, 2004 13:47 2. Algorithms and Data 27 (2) if the end of the text is reached, output the counter’s value and stop; (3) otherwise return to the main algorithm. The main part of the algorithm will utilize the search subroutine twice, by instructions of the form “callsearch-for ‘money’ ” and “callsearch-for ‘. ’ ”Contrast Figure 2.5 with Figure 2.6, in which the version with the subroutine is shown schematically. The processor that runs around doing things will now have to be slightly more sophisticated. When told to “call” a subroutine, it will stop whatever it has been doing, remember where it was, pick up the parameter(s), so to speak, and move increase counter check next few symbols check next few symbols initialize counter and pointer start NO YES YES Searching for end of sentence Searching for “money” NO advance pointer (including check for end of text) advance pointer (including check for end of text) output counter output counter stop stop END OF TEXT INSIDE TEXT INSIDE TEXT END OF TEXT Figure 2.5 Schematic flowchart for sentences with “money
28 I.Preliminaries Figure 2.6 Sentences with "money"using a start subroutine. subroutine search-for X initialize counter and INSIDE pointer check next TEXT few symbols call advance pointer search-for“money' (including check found NO for end of text) X? END OF TEXT call YES search-for“.” output counter increase return stop counter Subroutine Main algorithm over to the text of the subroutine.It will then do whatever the subroutine tells it to do,using the current value of a parameter wherever the subroutine refers to that parameter by its internal name (X,in our example).If and when the subroutine tells it to return,it will do just that;namely,it will return to the point following the"call" that led it to the subroutine in the first place,and will resume its duties from there. The Virtues of Subroutines Obviously,subroutines can be very economical as far as the size of an algorithm is concerned.Even in this simple example,the searching loop is written once but is used twice,whereas without it,of course,the algorithm would have had to include two detailed versions of that loop.This economy becomes considerably more significant for complex algorithms with many subroutines that are called from various places. Also,an algorithm can contain subroutines that call other subroutines,and so on. Thus,algorithmic structure is given a new dimension;there are not only nested loops but nested subroutines.Moreover,loops,conditional statements,sequential constructs,"goto"statements,and now subroutines,can all be interleaved,yielding algorithms of increasing structural complexity. Economy,however,is not the only advantage of subroutines.A subroutine can be viewed as a"chunk"of algorithmic material,some kind of building block,which
P1: GIG PE002-02drv PE002-Harel PE002-Harel-v4.cls March 18, 2004 13:47 28 I. Preliminaries subroutine search-for X check next few symbols found X? return stop output counter advance pointer (including check for end of text) NO YES END OF TEXT INSIDE TEXT start initialize counter and pointer call search-for “money” increase counter Subroutine Main algorithm call search-for “. ” Figure 2.6 Sentences with “money” using a subroutine. over to the text of the subroutine. It will then do whatever the subroutine tells it to do, using the current value of a parameter wherever the subroutine refers to that parameter by its internal name (X, in our example). If and when the subroutine tells it to return, it will do just that; namely, it will return to the point following the “call” that led it to the subroutine in the first place, and will resume its duties from there. ■ The Virtues of Subroutines Obviously, subroutines can be very economical as far as the size of an algorithm is concerned. Even in this simple example, the searching loop is written once but is used twice, whereas without it, of course, the algorithm would have had to include two detailed versions of that loop. This economy becomes considerably more significant for complex algorithms with many subroutines that are called from various places. Also, an algorithm can contain subroutines that call other subroutines, and so on. Thus, algorithmic structure is given a new dimension; there are not only nested loops but nested subroutines. Moreover, loops, conditional statements, sequential constructs, “goto” statements, and now subroutines, can all be interleaved, yielding algorithms of increasing structural complexity. Economy, however, is not the only advantage of subroutines. A subroutine can be viewed as a “chunk” of algorithmic material, some kind of building block, which
2.Algorithms and Data 29 once formed,can be used in another algorithmic chunk by a single instruction. This is just like saying that we have extended our repertoire of allowed elementary instructions.In the"money"counting example,once the search routine is there(and even beforehand,as long as it has been decided that such a routine will eventually be written)the instruction"call search-for'abc'"is,for every practical purpose,a new elementary instruction.Thus,subroutines are one way in which we can create our own abstractions,as is appropriate for the specific problem we are trying to solve. This is a very powerful idea,as it not only shortens algorithms but also makes them clear and well structured.Clarity and structure,as is repeatedly emphasized,are of the utmost importance in algorithmics,and many an effort is devoted to finding ways of imposing them on algorithm designers. In the same way that a user of a computer program typically knows nothing about the algorithms that it uses,a subroutine can be used as a"black box,"without knowing how it is implemented.All that the user of the subroutine has to know is what it does,but not how it does it.This greatly simplifies the problem,by reducing the amount of detail that needs to be kept in mind. Using subroutines,it is possible to develop a complex algorithm gradually,step by step.A typical algorithmic problem calls for a fully detailed solution that utilizes the allowed elementary actions only.The designer can work towards that goal gradually, by first devising a high-level algorithm,which uses"elementary"instructions that are not in the book.These are actually calls to subroutines that the designer has in mind,which are written later (or,perhaps,earlier).These subroutines,in turn, might use other instructions,which,not being elementary enough,are again regarded as calls to subroutines that are eventually written.At some point,all elementary instructions are at a sufficiently low level to be among those explicitly allowed.It is then that the gradual development process ends.This approach gives rise either to a "top-down"design,which,as just described,goes from the general to the specific,or to a"bottom-up"design,whereby one prepares the subroutines that will be needed, and then designs the more general routines that call them,thus working from the detailed to the general.There is no universal agreement as to which of these is the better approach to algorithmic design.The common feeling is that some kind of mixture should be used.We discuss this question further in Chapter 13. Returning for a moment to gastronomy,preparing a"chocolate mixture"might be a good candidate for a subroutine within the chocolate mousse recipe of Chapter 1. This would enable us to describe the recipe in the following way,where each of the four instructions is treated as a call to a subroutine (or should we say,a sub-recipe) whose text would then be written separately: (1)prepare chocolate mixture; (2)mix to produce chocolate-yolk mixture; (3)prepare foam of egg whites: (4)mix both to produce the mousse. It is worth pointing out that the book from which the mousse recipe was taken employs subroutines quite extensively.For example,pages 72-77 therein describe a number of recipes whose ingredients contain items such as Sweet Pastry Dough, Croissants,or Puff Pastry,for which the user is referred to previously given recipes dedicated to these very items
P1: GIG PE002-02drv PE002-Harel PE002-Harel-v4.cls March 18, 2004 13:47 2. Algorithms and Data 29 once formed, can be used in another algorithmic chunk by a single instruction. This is just like saying that we have extended our repertoire of allowed elementary instructions. In the “money” counting example, once the search routine is there (and even beforehand, as long as it has been decided that such a routine will eventually be written) the instruction “callsearch-for ‘abc’ ” is, for every practical purpose, a new elementary instruction. Thus, subroutines are one way in which we can create our own abstractions, as is appropriate for the specific problem we are trying to solve. This is a very powerful idea, as it not only shortens algorithms but also makes them clear and well structured. Clarity and structure, as is repeatedly emphasized, are of the utmost importance in algorithmics, and many an effort is devoted to finding ways of imposing them on algorithm designers. In the same way that a user of a computer program typically knows nothing about the algorithms that it uses, a subroutine can be used as a “black box,” without knowing how it is implemented. All that the user of the subroutine has to know is what it does, but not how it does it. This greatly simplifies the problem, by reducing the amount of detail that needs to be kept in mind. Using subroutines, it is possible to develop a complex algorithm gradually, step by step. A typical algorithmic problem calls for a fully detailed solution that utilizes the allowed elementary actions only. The designer can work towards that goal gradually, by first devising a high-level algorithm, which uses “elementary” instructions that are not in the book. These are actually calls to subroutines that the designer has in mind, which are written later (or, perhaps, earlier). These subroutines, in turn, might use other instructions, which, not being elementary enough, are again regarded as calls to subroutines that are eventually written. At some point, all elementary instructions are at a sufficiently low level to be among those explicitly allowed. It is then that the gradual development process ends. This approach gives rise either to a “top-down” design, which, as just described, goes from the general to the specific, or to a “bottom-up” design, whereby one prepares the subroutines that will be needed, and then designs the more general routines that call them, thus working from the detailed to the general. There is no universal agreement as to which of these is the better approach to algorithmic design. The common feeling is that some kind of mixture should be used. We discuss this question further in Chapter 13. Returning for a moment to gastronomy, preparing a “chocolate mixture” might be a good candidate for a subroutine within the chocolate mousse recipe of Chapter 1. This would enable us to describe the recipe in the following way, where each of the four instructions is treated as a call to a subroutine (or should we say, a sub-recipe) whose text would then be written separately: (1) prepare chocolate mixture; (2) mix to produce chocolate-yolk mixture; (3) prepare foam of egg whites; (4) mix both to produce the mousse. It is worth pointing out that the book from which the mousse recipe was taken employs subroutines quite extensively. For example, pages 72–77 therein describe a number of recipes whose ingredients contain items such as Sweet Pastry Dough, Croissants, or Puff Pastry, for which the user is referred to previously given recipes dedicated to these very items
30 I.Preliminaries It is fair to say that the power and flexibility provided by subroutines cannot be overestimated. Recursion One of the most useful aspects of subroutines,which to many people is also one of the most confusing,is recursion.By this we mean simply the ability of a subroutine, or procedure,to call itself.Now,this might sound absurd,since how on earth does our processor come any closer to solving a problem by being told,in the midst of trying to solve that problem,to leave everything and start solving the same problem all over again? The following example should aid us in resolving this paradox,and it might help if we say at the start that the resolution is based on the very same property of algorithms mentioned earlier:the same text (in this case,that of the recursive subroutine)can correspond to many portions of the process described by it.Iterative constructs are one way of mapping lengthy processes on to short texts;recursive subroutines are another. The example is based on a rather ancient puzzle known as the Towers of Hanoi, originating with Hindu priests in the great temple of Benares.Suppose we are given three towers,or to be more humble,three pegs,A,B,and C.On the first peg,A, there are three rings piled in descending order of magnitude,while the others are empty(see Figure 2.7).We are interested in moving the rings from A to B,perhaps using C in the process.By the rules of the game,rings are to be moved one at a time,and at no instant may a larger ring be placed atop a smaller one.This simple puzzle can be solved as follows: move A to B: move A to C: move B to C; move A to B; move C to A; move C to B; move A to B. Before proceeding,we should first convince ourselves that these seven actions really do the job,and we should then try the same puzzle with four rather than three rings on peg A(the number of pegs does not change).A moderate amount of work should suffice for you to discover a sequence of 15 "move X to Y"actions that solve the four-ring version. Such puzzles are intellectually challenging,and those who enjoy puzzles may like to consider the original Hindu version which involves the same three pegs, Figure 2.7 The Towers of Hanoi with three rings
P1: GIG PE002-02drv PE002-Harel PE002-Harel-v4.cls March 18, 2004 13:47 30 I. Preliminaries It is fair to say that the power and flexibility provided by subroutines cannot be overestimated. ■ Recursion One of the most useful aspects of subroutines, which to many people is also one of the most confusing, is recursion. By this we mean simply the ability of a subroutine, or procedure, to call itself. Now, this might sound absurd, since how on earth does our processor come any closer to solving a problem by being told, in the midst of trying to solve that problem, to leave everything and start solving the same problem all over again? The following example should aid us in resolving this paradox, and it might help if we say at the start that the resolution is based on the very same property of algorithms mentioned earlier: the same text (in this case, that of the recursive subroutine) can correspond to many portions of the process described by it. Iterative constructs are one way of mapping lengthy processes on to short texts; recursive subroutines are another. The example is based on a rather ancient puzzle known as the Towers of Hanoi, originating with Hindu priests in the great temple of Benares. Suppose we are given three towers, or to be more humble, three pegs, A, B, and C. On the first peg, A, there are three rings piled in descending order of magnitude, while the others are empty (see Figure 2.7). We are interested in moving the rings from A to B, perhaps using C in the process. By the rules of the game, rings are to be moved one at a time, and at no instant may a larger ring be placed atop a smaller one. This simple puzzle can be solved as follows: move A to B; move A to C; move B to C; move A to B; move C to A; move C to B; move A to B. Before proceeding, we should first convince ourselves that these seven actions really do the job, and we should then try the same puzzle with four rather than three rings on peg A (the number of pegs does not change). A moderate amount of work should suffice for you to discover a sequence of 15 “move X to Y ” actions that solve the four-ring version. Such puzzles are intellectually challenging, and those who enjoy puzzles may like to consider the original Hindu version which involves the same three pegs, A BC Figure 2.7 The Towers of Hanoi with three rings