Recursion, Iteration, and Algebra
Author: Joel Neely
Date: [
1-Aug-2001 22-Dec-2001 02-Jan-2002 03-Jan-2002 07-Jan-2002
]
Version: 1.4
Part: 1 | 2
Contents
- Introduction
- Recursion, Iteration and State
- Flat Block Total
- The Strategy
- Nested Block Total
- A Final Alternative
- Conclusions
Introduction
Mathematics and computing courses and articles sometimes resemble instruction by intimidation. Students (or readers) are shown an elegant proof, formula, or algorithm and then told, "Go thou and do likewise!" without any real explanation of HOW to do so. This is very unfortunate, because programming is not like a joke, where either you get it or you don't. It is a skill that can be learned (and practiced) in a step-by-step manner.
To solve an equation in algebra, we usually massage it through a series of changes to produce an equivalent equation whose form is so simple that its solution is obvious. In the same way, we can take a program and restructure the code to improve performance, generality, or other useful properties.
To switch metaphors, programming is sometimes like a performance of stage magic. The result may appear amazing and inscrutable, but it is easy to understand after you see how the illusion was constructed. The primary purpose of this article is to illustrate some techniques for incrementally refactoring Rebol scripts from recursive to iterative form. (Some reasons for doing so are discussed along the way. The old stereotypical assumption that recursion is always complicated and expensive is NOT a good reason!) The secondary goal is to illustrate the power of the refactoring approach itself.
This is the first article in a small series that will explore the issues outlined above. It may be a bit tedious; we'll be moving at a very slow pace to lay our foundations carefully. Subsequent articles will build on this one (at a higher rate of speed! ;-) and show some other uses for the techniques we'll consider here.
Recursion, Iteration and State
Recursion and iteration are different ways to cause the evaluation of an expression to re-occur as needed. Recursion often appears in functional-style definitions or divide-and-conqure explanations of an algorithm. Programming with recursion involves the idea of "vertical" self-reference, as in a data structure that has substructures similar to itself, or a function which invokes itself. In contrast, iteration simply involves the notion of "horizontal" repetition of some concept, such as an expression to be evaluated repeatedly or a data structure which contains a sequence of identically-structured components.
In theory, recursion and iteration are equivalent; anything we can do with one, we can do with the other. In practice, this is like saying that all loops can be written using only WHILE. That may be true, but having LOOP, REPEAT, and FOREACH certainly makes programming more convenient! Each is the best tool for some purposes, which is also true for recursion and iteration.
For instance, we could use the implicit iteration of FOREACH to write a function that prints the elements in a block:
printblock: func [b [block!]] [
foreach item b [print item]
]
If Rebol didn't have FOREACH pre-defined, we could use explicit iteration to write this function as:
iprintblock: func [b [block!]] [
while [not empty? b] [
print first b
b: next b
]
]
We could also use recursion to obtain the same output:
rprintblock: func [b [block!]] [
either empty? b [
exit
][
print first b
rprintblock next b
]
]
These last two functions illustrate the basic relationships between recursion and iteration. They are similar in that both:
- test for an exit condition (EMPTY? B);
- perform an operation (PRINT FIRST) on the current data (B), and
- manipulate the data (NEXT B) in preparation for the next test of the exit condition.
They are different in how they:
- terminate, either implicitly (falling out of the WHILE) or explicitly (EXITing RPRINTBLOCK when the exit condition occurs), and
- start the next evaluation, either implicitly (via the definition of WHILE) or explicitly (by RPRINTBLOCK invoking itself).
At another level, recursion and iteration differ in how they handle the state of an evaluation — the "where we are and what we know" information available at any moment during evaluation. We'll look into this when we take on some specific problems below.
It is often relatively easy to take a specification and construct a simple, correct recursive function. We can then refactor it into iterative form to improve some aspect of its performance, such as its storage or time requirements. This approach makes a very useful addition to our toolkit of programming ideas.
Let's begin with a trivially simple recursive algorithm, and develop a strategy for refactoring it into an iterative form. After doing so, we can apply that strategy to more complex cases.
Flat Block Total
The first task is this: given a flat (single-level) block of numbers, calculate the block total (sum of the numbers in the block). Of course, most Rebol programmers could immediately write this as:
blocktotal: func [arg-block [block!] /local total] [
total: 0
foreach number arg-block [
total: total + number
]
total
]
(with some variation in naming and formatting styles). Some reasons for beginning with such a simple example are:
- we don't have to spend time trying to understand the problem;
- we know where we want our development efforts to end up, so we'll know when we get there; and
- we can concentrate on the process we use to arrive at that easy-to-understand result.
In a purely recursive fashion, we can say that the block total is calculated by two rules:
- If the block is empty, the block total is zero.
- If the block is not empty, the block total is the first number in the block plus the block total of the rest of the block.
This specification can be translated directly into a recursive Rebol function:
bt: func [b [block!]] [
if empty? b [0 ]
if not empty? b [(first b) + bt next b]
]
Since EMPTY? B has no side effects, we can replace the consecutive IF and IF NOT with EITHER for a slightly simpler version:
bt: func [b [block!]] [
either empty? b [
0
][
(first b) + bt next b
]
]
We can visualize its evaluation by progressive rewriting; in each rewriting step, we replace an expression using BT with one of the two sub-expressions in BT's body, substituting the actual value for the argument. Using parentheses to show the order of the replacements, we have:
bt [1 8 5 2]
= 1 + (bt [8 5 2])
= 1 + (8 + (bt [5 2]))
= 1 + (8 + (5 + (bt [2])))
= 1 + (8 + (5 + (2 + (bt []))))
= 1 + (8 + (5 + (2 + 0)))
= 1 + (8 + (5 + 2))
= 1 + (8 + 7)
= 1 + (15)
= 16
The argument's actual value at every step is the "what we know" part of the state. The parentheses and plus signs imply the "where we are" part of the state — the previously-begun evaluations of BT that have not yet completed.
This pattern of descending into nested expressions and completing the pending evaluations on the way back out is common in pure recursive functions. During the first five steps the function is navigating through the block finding the numbers; in the remaining four steps it completes the additions that were left "on hold". Although Rebol doesn't evaluate expressions by this explicit rewriting process, the information we're visualising does have to be represented somehow. The processing and memory required to represent the pending work and related data are costs of using recursion.
That said, we can identify two motivations for rewriting a recursive function into iterative form:
- There's often a trade-off between the simplicity of the recursive form and the speed and/or storage economy of the iterative form. If we know how to convert between the two, we can choose the form that is most suited for any given application.
- Being able to see both versions often can deepen our understanding of the problem and its solution(s), which is almost always A Good Thing.
Later in this series of articles we'll see that these aren't the only reasons, but that's another story. For now, let's concentrate more on the "how" than the "why".
Create a helper function
The first step in our refactoring strategy seems like a step backwards. To hide the changes from other expressions that might use BT, we start by creating a local function inside BT that does the actual work (commonly known as a "helper function"). Using a dot prefix to name corresponding functions and arguments, we can write:
bt: func [b [block!] /local .bt] [
do .bt: func [.b [block!]] [
either empty? .b [
0
][
(first .b) + .bt next .b
]
] b
]
This step converts the original BT into a interface "wrapper" around the helper function, which we can now restructure at will (as long as we maintain correctness!) Visualizing this version is almost identical to the original, except for the name changes and a first step from BT to .BT, so won't be included here.
Push the helper's state into its arguments
The next refactoring step eliminates any pending work waiting for a subordinate evaluation of .BT to complete. Another way of saying this is that we're pushing as much state as possible into the arguments (what we know) and eliminating the need to resume the caller (where we are). This transformation is completed when the arguments contain everything needed to finish the evaluation.
To clarify, let's temporarily alter the helper function to print its argument...
bt: func [b [block!] /local .bt] [
do .bt: func [.b [block!]] [
print mold .b
either empty? .b [
0
][
(first .b) + .bt next .b
]
] b
]
to get the following output:
>> bt [1 8 5 2]
[1 8 5 2]
[8 5 2]
[5 2]
[2]
[]
== 16
>>
The argument printed at each step shows the remainder of the block to be traversed, but not the additions waiting to be completed. Therefore we know that the arguments are not yet telling the whole story.
One of the simplest ways to move state into the arguments is to use "accumulators" — one or more arguments that contain the partial results of work done earlier ("on the way in") rather than later ("on the way out"). Addition is associative; a sum can be accumulated either left-to-right or right-to-left. Therefore,
(1 + (8 + (5 + (2 + (0)))))
is equivalent to
(((((0) + 1) + 8) + 5) + 2)
We can change .BT to accumulate a running total of the numbers already visited in the block. By passing the running total and the remainder of the block as arguments to each recursive evaluation, we have a complete picture of what is already done and what remains to be done.
This revised strategy (adding a block's content to a running total) can be described as follows:
- If the block is empty, the running total is the answer.
- If the block is non-empty, create a new running total (the old running total plus the first number in the block) and obtain the result by adding the rest of the block to that new running total.
With this new spec for the helper function (continuing to print all arguments for the moment), we now have
bt: func [b [block!] /local .bt] [
do .bt: func [rt [number!] .b [block!]] [
print [rt mold .b]
either empty? .b [
rt
][
.bt rt + first .b next .b
]
] 0 b
]
Using the same data, our evaluation prints a very different picture:
>> bt [1 8 5 2]
0 [1 8 5 2]
1 [8 5 2]
9 [5 2]
14 [2]
16 []
== 16
>>
Since we can look the arguments at any step and know exactly how to complete the entire evaluation, all of the necessary state has now been moved into .BT's argument list.
Now consider the structure of .BT itself; every evaluation path ends either in:
- a non-recursive expression whose value is the net result for the entire evaluation, or
- a single recursive use of .BT whose value is the net result,
and .BT contains no other recursion. This means that .BT is now in "tail recursive" form, which prepares our code for the next step.
Change helper arguments into parent locals
Now that we've pushed the state of the recursive helper function into its arguments, let's eliminate the arguments! We'll replace each argument of the helper function with a local variable in the original function. (In the case of .B, we simply use B, which is already local to BT.) Instead of passing arguments to .BT, we explicitly set the appropriate local variables. The values of those variables aren't saved and restored in the same way that function arguments would be; this is safe because this version won't need those previous values "on the way back out".
We can also discard the tracing code PRINT [RT MOLD B] from the beginning of .BT, after verifying that the output is identical to that of the previous version.
bt: func [b [block!] /local .bt rt] [
rt: 0
do .bt: func [] [
either empty? b [
rt
][
rt: rt + first b
b: next b
.bt
]
]
]
The finish line is in sight!
Replace the helper with a loop
We're now ready to eliminate the helper function. The current version of .BT has the following structure:
recfun: func [] [
either exitcondition [
finalexpression
][
recurringexpression
recfun
]
]
RECURRINGEXPRESSION is repeatedly evaluated until EXITCONDITION is true, at which point FINALEXPRESSION is evaluated as the final answer. Based on our experience with IPRINTBLOCK and RPRINTBLOCK, we can rewrite this as:
while [not exitcondition] [
recurringexpression
]
finalexpression
This revision give us
bt: func [b [block!] /local .bt rt] [
rt: 0
while [not empty? b] [
rt: rt + first b
b: next b
]
rt
]
in which the recursion has been completely replaced by iteration.
Simplify the loop
In some cases, the form of the iteration allows us to simplify further by using a special-purpose iterative function. Since this example is clearly acting on each element of the argument block, we can rewrite it (one last time!) to
bt: func [b [block!] /local rt] [
rt: 0
foreach item b [
rt: rt + item
]
rt
]
We won't always have such shortcuts, but it's nice to take advantage of them when we do.
The Strategy
To recap, our strategy for transforming a recursive function into an iterative one involves the following steps:
- Create a helper function that actually does the work, and change the original function into a wrapper around that helper.
- Push the state of the helper function into its arguments, so that there's nothing left to do after a recursive evaluation. We know we're finished when the arguments alone contain everything to finish the entire evaluation with no "going back".
- Change the arguments of the helper function into local variables of the original function.
- Replace the helper function by a corresponding WHILE expression.
- Replace the WHILE expression with a corresponding special-purpose loop function (such as FOREACH) whenever possible.
For our first test problem, all of this may resemble using a sledge hammer to crack an egg. Just as in elementary algebra class, we've proceeded in very tiny steps which allow us to verify our work in (agonizing ;-) detail. The payoff will come if we can use the same strategy on less obvious recursive functions. That's what we'll tackle next.
Nested Block Total
As a small step up in complexity, let's sum the numbers in a block that can have arbitrary structure, such as
[[[3] 1] [4 7]]
Now we need a definition that deals with an empty block, a non-empty block, and a nested sub-block. The rules for a nested block total (assuming that our block contains only numbers and sub-blocks!) may be written as follows:
- If the block is empty, the total is zero.
- If the block is non-empty, and the first element is a nested block, add the nested block total of that first element to the nested block total of the rest of the main block.
- If the block is non-empty, and the first element is not a block, add that first element to the nested block total of the rest of the block.
Beginning with a brute-force translation, we obtain:
nbt: func [b [block!]] [
if empty? b [
return 0
]
if all [not empty? b block? first b] [
return (nbt first b) + nbt next b
]
if all [not empty? b not block? first b] [
return (first b) + nbt next b
]
]
Before eliminating the recursion, we'll simplify the code as before. We'll continue working in very tiny steps, both to minimize the chance of error and to keep the focus on our rewriting strategy.
1) Factor out a common subexpression (NOT EMPTY? B) in the two IF ALL expressions:
nbt: func [b [block!]] [
if empty? b [
return 0
]
if not empty? b [
if block? first b [
return (nbt first b) + nbt next b
]
if not block? first b [
return (first b) + nbt next b
]
]
]
2) Replace consecutive IF BLOCK?... and IF NOT BLOCK?... expressions with a single EITHER BLOCK?... expression:
nbt: func [b [block!]] [
if empty? b [
return 0
]
if not empty? b [
either block? first b [
return (nbt first b) + nbt next b
][
return ( first b) + nbt next b
]
]
]
3) Do the same with EMPTY? B versus NOT EMPTY? B:
nbt: func [b [block!]] [
either empty? b [
return 0
][
either block? first b [
return (nbt first b) + nbt next b
][
return ( first b) + nbt next b
]
]
]
4) Cache the value of a repeated expression (FIRST B) in a local variable (FRONT) — as with the IF-to-EITHER revision, this is safe only if that expression's value is stable for consecutive evaluations:
nbt: func [b [block!] /local front] [
either empty? b [
return 0
][
either block? front: first b [
return (nbt front) + nbt next b
][
return front + nbt next b
]
]
]
5) Eliminate RETURN before the last expression in any path through a function:
nbt: func [b [block!] /local front] [
either empty? b [
0
][
either block? front: first b [
(nbt front) + nbt next b
][
front + nbt next b
]
]
]
Notice that the function's body has a nice form. It is a decision tree which selects one expression whose value is the result of the entire evaluation (although the recursions are still present).
It takes a surprising number of steps to visualize an evaluation of this function by rewriting. The recursive structure requires a separate rewriting step for every sub-block as well as for every number. Again, in the interest of care, we'll only rewrite the left-most subexpression using NBT in each step below.
nbt [[[3] 1] [4 7]]
= (nbt [[3] 1]) + (nbt [[4 7]])
= ((nbt [3]) + (nbt [1])) + (nbt [[4 7]])
= ((3 + (nbt [])) + (nbt [1])) + (nbt [[4 7]])
= ((3 + 0) + (nbt [1])) + (nbt [[4 7]])
= (3 + (nbt [1])) + (nbt [[4 7]])
= (3 + (1 + (nbt []))) + (nbt [[4 7]])
= (3 + (1 + 0)) + (nbt [[4 7]])
= (3 + 1) + (nbt [[4 7]])
= 4 + (nbt [[4 7]])
= 4 + ((nbt [4 7]) + (nbt []))
= 4 + ((4 + (nbt [7])) + (nbt []))
= 4 + ((4 + (7 + (nbt []))) + (nbt []))
= 4 + ((4 + (7 + 0)) + (nbt []))
= 4 + ((4 + 7) + (nbt []))
= 4 + (11 + (nbt []))
= 4 + (11 + 0)
= 4 + 11
= 15
Another worthwhile exercise (left to the reader) is to insert PRINT MOLD B into the definition of NBT to see just how much state information we'll have to find and put in the arguments! (Hint: we not only have all of the pending additions, but also multiple subexpressions containing NBT.)
Starting with this last recursive version, we'll apply the same refactoring strategy as before, and pick up some additional ideas along the way.
Create a helper function
Clone the function to produce the helper, and then DO the helper on the arguments of the original function.
nbt: func [b [block!] /local .nbt] [
do .nbt: func [.b [block!] /local front] [
either empty? .b [
0
][
either block? front: first .b [
(.nbt front) + .nbt next .b
][
front + .nbt next .b
]
]
] b
]
Since the results are so similar, we won't visualize this version.
Push the helper's state into its arguments
We can refactor the running total into an accumulator argument, just as we did with the first problem. It is easy to do that with the last branch of .NBT (it is identical to the last branch in the previous problem). Adding the value of FRONT to the previous running total, then passing that sum on as the new running total, transforms
front + .nbt next .b
into
.nbt rt + front next .b
However, the second branch — the one with two recursive calls — takes a bit more effort. Evaluating
.nbt rt front
would give us a sum which included the first nested block. We could then use that result as the new running total for the remainder of the block. That means that the second branch would be rewritten as
.nbt .nbt rt front next .b
Based on those two observations, we can modify .NBT to use a running total as its first argument and obtain:
nbt: func [b [block!] /local .nbt] [
do .nbt: func [rt [number!] .b [block!] /local front] [
either empty? .b [
rt
][
either block? front: first .b [
.nbt .nbt rt front next .b
][
.nbt rt + front next .b
]
]
] 0 b
]
However, we haven't finished pushing all of the state into the arguments — the second branch still recursively evaluates .NBT twice. Remember that the goal is to have a single recursive evaluation that leaves no work remaining to be done when it completes.
Using an accumulator is only one strategy for moving state into the argument list, and it doesn't seem like a viable choice for the nested sub-block in that second branch. Another strategy is to create a new argument which explicitly contains any work which we're putting off until later. Instead of having a single argument Block, we'll distinguish between the CURrent block and the PENding blocks to be totalled in the future.
When we encounter a nested block (via BLOCK? FRONT), we'll push the remainder of the current block (NEXT CUR) into a "to-do list", and continue working on FRONT as if it were our only problem. After we've added the contents of FRONT to the running total, we'll check the to-do list and resume anything we find there.
We can combine the rest of the CURrent block with any previous PENding work by evaluating REDUCE [NEXT CUR PEN] and later splitting them apart via FIRST (for the saved value of NEXT CUR) and SECOND (for the previous value of PEN). This strategy gives us our next version:
nbt: func [b [block!] /local .nbt] [
do .nbt: func [
rt [number!] cur [block!] pen [block!]
/local front
][
either empty? cur [
either empty? pen [
rt
][
.nbt rt first pen second pen
]
][
either block? front: first cur [
.nbt rt front reduce [next cur pen]
][
.nbt rt + front next cur pen
]
]
] 0 b []
]
Inserting PRINT [RT "," MOLD CUR "," MOLD PEN] at the beginning of .NBT shows how the last two arguments interact to hold all state information during an evaluation:
>> nbt [[[3] 1] [4 7]]
0 , [[[3] 1] [4 7]] , []
0 , [[3] 1] , [[[4 7]] []]
0 , [3] , [[1] [[[4 7]] []]]
3 , [] , [[1] [[[4 7]] []]]
3 , [1] , [[[4 7]] []]
4 , [] , [[[4 7]] []]
4 , [[4 7]] , []
4 , [4 7] , [[] []]
8 , [7] , [[] []]
15 , [] , [[] []]
15 , [] , []
== 15
Finally we have a version in tail-recursive form, and are ready for the next step in our recipe.
Change helper arguments into parent locals
Converting all of the helper's arguments (and locals) to locals of the main function gets us one step closer to the end:
nbt: func [b [block!] /local .nbt rt cur pen front] [
rt: 0
cur: b
pen: []
do .nbt: func [] [
either empty? cur [
either empty? pen [
rt
][
cur: first pen
pen: second pen
.nbt
]
][
either block? front: first cur [
pen: reduce [next cur pen]
cur: front
.nbt
][
rt: rt + front
cur: next cur
.nbt
]
]
]
]
There's one small but important bit of subtlety; we can't set a local word to a new value as long as its old value is needed. In the second branch, the new values of both CUR and PEN are taken from the old value of PEN, so PEN is set last. In the third branch, the new values of both PEN and CUR require the old value of CUR, so CUR is set last.
Replace the helper with a loop
There are several ways to replace .NBT with a loop. Since the exit case (the first branch) is inside nested EITHER expressions, one of the simplest is:
nbt: func [b [block!] /local rt cur pen front ] [
rt: 0
cur: b
pen: []
while [true] [
either empty? cur [
either empty? pen [
return rt
][
cur: first pen
pen: second pen
]
][
either block? front: first cur [
pen: reduce [next cur pen]
cur: front
][
rt: rt + front
cur: next cur
]
]
]
]
The only real change is that we must explicitly RETURN the final value.
Simplify the loop
In this case the body of the loop is optimal, in the sense that no condition is tested more than once. Changing the loop to perform the complete exit tests in the WHILE form would actually make is slower, since both conditions (both CUR and PEN being empty) are also needed to select an action within the loop and would be tested redundantly.
The only simplification we'll make is cosmetic:
nbt: func [b [block!] /local rt cur pen front ] [
rt: 0
cur: b
pen: []
forever [
either empty? cur [
either empty? pen [
return rt
][
cur: first pen
pen: second pen
]
][
either block? front: first cur [
pen: reduce [next cur pen]
cur: front
][
rt: rt + front
cur: next cur
]
]
]
]
since WHILE [TRUE] may be abbreviated using the FOREVER mezzanine function.
A Final Alternative
So far we've used two strategies for pushing state into the helper's arguments:
- Create an accumulator argument to pass in partial results (instead of performing work after returning from a recursive evaluation).
- Create a "to-do list" argument to pass in pending work (instead of performing multiple recursive evaluations).
Just to show that there are still more alternatives (and to prove that refactoring doesn't have to be done at snail speed ;-), we'll use a different state-management strategy to produce another solution to the last problem.
Argument "rewriting"
We've been rewriting/refactoring the code to produce a desired effect, so why not allow the function to rewrite/refactor its own arguments? Of course, the rewriting can't destroy any information about the original structure that is actually relevant to the solution! In the case of the Nested Block Total problem, let's assume that the only constraints are to avoid losing contents (the numbers at the leaves), to keep them in the same order, and to avoid modifying the original block passed as an argument.
When we traced the previous solution (with the inserted PRINT of the arguments), you may have noticed that there were some empty blocks being passed back and forth. This occurs because the original PENding list was empty, and also occurs whenever the CURrent block contains only a nested block. There's a classic time-for-space tradeoff here: the previous strategy avoided the memory management issues of copying potentially large blocks, but paid for those savings by occasionally handling references to empty blocks.
These thoughts suggest an alternative strategy, assuming that we've already set up an accumulator argument for the running total. Only the third branch (handling a nested block) is different.
- If the block is empty, the running total is the final result.
- If the block is non-empty and the first element is a number, then add that number to the running total and continue with the rest of the block.
- If the block is non-empty and the first element is a block, then create a new block with one level of nesting removed from the first element and try again.
Fortunately for this exercise, COMPOSE is a native that will unwrap blocks and create new blocks, making the revised third branch easy to implement, as follows:
nbt: func [b [block!] /local .nbt] [
do .nbt: func [rt [number!] .b [block!] /local front] [
print [rt mold .b]
either empty? .b [
rt
][
either block? front: first .b [
.nbt rt compose [(front) (next .b)]
][
.nbt rt + front next .b
]
]
] 0 b
]
This version shows the effect of the argument rewriting:
>> nbt [[[3] 1] [4 7]]
0 [[[3] 1] [4 7]]
0 [[3] 1 [4 7]]
0 [3 1 [4 7]]
3 [1 [4 7]]
4 [[4 7]]
4 [4 7]
8 [7]
15 []
== 15
Eliminating the helper function (and the argument printing) from this version gives us:
nbt: func [b [block!] /local rt front ] [
rt: 0
while [not empty? b] [
either block? front: first b [
b: compose [(front) (next b)]
][
rt: rt + front b: next b
]
]
rt
]
Note that this version can't be refactored into a simple FOREACH loop; some passes through the loop may restructure the argument block instead of adding the first element and moving on.
Conclusions
We've explored an approach for refactoring recursive functions into iterative form, both as a tool for creating Rebol functions and as a way of understanding them. Our top-level strategy consists of five steps:
- Create a helper function.
- Push helper's state into its arguments.
- Replace helper arguments with parent locals.
- Replace the helper with a loop.
- Simplify the loop.
We've seen three sub-strategies for manipulating state in the second step; we can use:
- Accumulator arguments (to do work early).
- To-do-list argument (to hold pending work).
- Argument rewriting (to maintain only the significant parts of the pending work).
As mentioned earlier, we've moved at a snail's pace through some fairly easy problems. Now that we have a strategy that we've seen at work on simple cases, the payoff will come as we apply the same approach on more complex problems. That's the task of future articles in this series.
To whet your appetite, dear reader and fellow Rebolite, let me leave you with a couple of questions:
- What difference would it make if we had been trying to calculate the product of all the numbers in a block, rather than the sum?
- How can we check whether two blocks contain the same data (in the same order), regardless of the nesting structures of those blocks?
We'll examine those in the next article. Happy refactoring!