## How to Replace Any Recursion with Simple Iteration or Unlimited Iteration with its Own Stack, in FB

Forum for discussion about the documentation project.
fxm
Posts: 8907
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

### How to Replace Any Recursion with Simple Iteration or Unlimited Iteration with its Own Stack, in FB

Iteration and recursion are two very useful ways to program, especially to perform a certain number of times a certain script, and thus allow optimization of the code. If iteration is relatively easy to understand, recursion is a concept not necessarily obvious at the beginning.
When speaking of a recursive procedure (subroutine or function), we refer to a syntactic characteristic: the procedure, in its own definition, refers to itself (it calls itself).
But when talking about recursive process, linear or tree, we are interested in the process flow, not in the syntax of the procedure's writing.
Thus, a procedure can have a recursive definition but correspond to an iterative process.

Some treatments are naturally implemented as a recursive algorithm (although this is not always the most optimal solution).
The main problem of the recursive approach is that it consumes potentially a lot of space on the execution stack: from a certain level of "depth" of recursion, the space allocated for the execution stack of the thread is exhausted, and causes an error of type "stack overflow".
Repeatedly calling the same procedure can also make the execution slower, although this may make the code easier.
To increase the speed of execution, simple recursive algorithms can be recreated in little more complicated iterative algorithms using loops that execute much faster.

What is the use of recursion if it increases the execution time and memory space compared to an iterative solution?
There are still cases where it is not possible to do otherwise, where iterative translation does not exist or, where it exists, is much heavier to implement (requiring for example a dynamic storage capacity to substitute for the execution stack).

1) Recursion and Iteration
Recursion and iteration both repeatedly execute the instruction set:
• Recursion occurs when an instruction in a procedure calls the procedure itself repeatedly.
• Iteration occurs when a loop executes repeatedly until the control condition becomes false.
The main difference between recursion and iteration is that recursion is a process always applied to a procedure, while iteration is applied to a set of instructions to execute repeatedly.
1.1) Definition of Recursion
FreeBASIC allows a procedure to call itself in its code. This means that the procedure definition has a procedure call to itself. The set of local variables and parameters used by the procedure are newly created each time the procedure is called and are stored at the top of the execution stack. But every time a procedure calls itself, it does not create a new copy of that procedure. The recursive procedure does not significantly reduce the size of the code and does not even improve the memory usage, but it does a little bit compared to iteration.

To end recursion, a condition must be tested to force the return of the procedure without giving a recursive call to itself. The absence of a test of a condition in the definition of a recursive procedure would leave the procedure in infinite recursion once called.

Note: When the parameters of a recursive procedure are passed by reference, take care to work with local variables when the code body needs to modify their values.

1. Simple example with a recursive function which returns the factorial of the integer:
The code body of the recursive function is defined by using the recursive definition of the factorial function:
Case (n = 0) : factorial(0) = 1
Case (n > 0) : factorial(n) = n * factorial(n-1)
The first line allows to determine the end condition: 'If (n = 0) Then Return 1'
The second line allows to determine the statement syntax which calls the function itself: 'Return n * factorial(n - 1)'

Full code:

Code: Select all

`Function recursiveFactorial (Byval n As Integer) As Integer  If (n = 0) Then                         '' end condition    Return 1  Else                                    '' recursion loop    Return n * recursiveFactorial(n - 1)  '' recursive call  End IfEnd Function`
1.2) Definition of Iteration
Iteration is a process of repeatedly executing a set of instructions until the iteration condition becomes false.
The iteration block includes the initialization, the comparison, the execution of the instructions to be iterated and finally the update of the control variable.
Once the control variable is updated, it is compared again and the process is repeated until the condition in the iteration is false.
Iteration blocks are "for" loop, "while" loop, ...

The iteration block does not use the execution stack to store the variables at each cycle. Therefore, the execution of the iteration block is faster than the recursion block. In addition, iteration does not have the overhead of repeated procedure calls that also make its execution faster than a recursion.
The iteration is complete when the control condition becomes false.

1. Simple example with a iterative function which returns the factorial of the integer:
The code body of the iterative function is defined by using the iterative of the factorial function:
Case (n = 0) : factorial(0) = 1
Case (n > 0) : factorial(n) = (1) * ..... * (n - 2) * (n - 1) * (n)
The first line allows to determine the cumulative variable initialization: 'result = 1'
The second line allows to determine the statement syntax which accumulates: 'result = result * I'

Full code:

Code: Select all

`Function iterativeFactorial (Byval n As Integer) As Integer  Dim As Integer result = 1  '' variable initialization  For I As Integer = 1 To n  '' iteration loop    result = result * I      '' iterative accumulation  Next I  Return resultEnd Function`
2) Replace Recursion with Iteration
Whatever the problem to be solved, there is the choice between the writing of an iterative procedure and that of a recursive procedure. If the problem has a natural recursive structure, then the recursive program is a simple adaptation of the chosen structure. This is the case of the factorial functions (seen above) for example. The recursive approach, however, has drawbacks: some languages ​​do not allow recursion (like the machine language!), and a recursive procedure is often expensive in memory (for execution stack) as in execution time.

These disadvantages can be overcome by transforming the recursive procedure, line by line, into an iterative procedure: it is always possible.
Replace a recursion with an iteration allows to suppress the limitation on the number of cycles due to the execution stack size available. But for an iteration with its own storage stack, the time spent to calls to the procedures for pushing and pulling stack data is generally greater than the one for passing the parameters of a recursive procedure at each calling cycle.

The complexity of the iterative procedure obtained by such a transformation depends on the structure of the recursive procedure:
• for some form of recursive procedure (see below the tail recursion), the transformation into an iterative procedure is very simple by means of just defining local variables corresponding to the parameters of the recursive procedure (passed arguments),
• at opposite for other forms of recursive procedure (non-tail recursions), the use of a user storage stack in the iterative procedure is necessary to save the context, as the recursive calls do (values ​​of the passed arguments at each call):
- when executing a recursive procedure, each recursive call leads to push the context on execution stack,
- when the condition of stopping recursion occurs, the different contexts are progressively popped from execution stack to continue executing the procedure.
2.1) Replace Tail Recursion with Simple Iteration
The recursive procedure is a tail recursive procedure if the only recursive call is at the end of the recursion and is therefore not followed by any other statement:
- for a recursive subroutine, the only recursive call is at the end of the recursion,
- for a recursive function, the only recursive call is at the end of the recursion and consists in taking into account the return of the function without any other additional operation on it.
A tail recursive procedure is easy to transform into an iterative procedure.
The principle is that if the recursive call is the last instruction of a procedure, it is not necessary to keep on the execution stack the context of the current call, since it is not necessary to return to it:
- it suffices to replace the parameters by their new values, and resume execution at the beginning of the procedure,
- the recursion is thus transformed into iteration, so that there is no longer any risk of causing an overflow of the execution stack.
Some non-tail recursive procedures can be transformed into tail recursive procedures, sometimes with a little more complex code, but even before they are subsequently transformed into iterative procedures, these tail recursive procedures often already gain in memory usage and execution time.

1. Example with the simple "factorial" recursive function:
Non-tail recursive form (already presented above):

Code: Select all

`Function recursiveFactorial (Byval n As Integer) As Integer  If (n = 0) Then                         '' end condition    Return 1  Else                                    '' recursion loop    Return n * recursiveFactorial(n - 1)  '' recursive call  End IfEnd Function`
This function has a non-tail recursive form because even though the recursive call is at the end of the function, this recursive call is not the last instruction of the function because one has to multiplied again by 'n' when 'recursiveFactorial(n - 1)' is got.
This calculation is done when popping context from execution stack.

It is quite easy to transform this function so that the recursion is a tail recursion.
To achieve this, it is necessary to add a new parameter to the function: the 'result' parameter which will serve as accumulator:

Code: Select all

`Function tailRecursiveFactorial (Byval n As Integer, Byval result As Integer = 1) As Integer  If (n = 0) Then                                     '' end condition    Return result  Else                                                '' recursion loop    Return tailRecursiveFactorial(n - 1, result * n)  '' tail recursive call  End IfEnd Function`
This time, the calculation is done when pushing context on execution stack.

Tail recursion is more explicit by calculating 'n - 1' and 'result * n' just before the recursive call:

Code: Select all

`Function explicitTailRecursiveFactorial (Byval n As Integer, Byval result As Integer = 1) As Integer  If (n = 0) Then                                     '' end condition    Return result  Else                                                '' recursion loop    result = result * n    n = n - 1    Return explicitTailRecursiveFactorial(n, result)  '' tail recursive call  End IfEnd Function`

Now it is sufficient to resume execution at the beginning of the procedure by a 'Goto begin' instead of the function call, to obtain an iterative function:

Code: Select all

`Function translationToIterativeFactorial (Byval n As Integer, Byval result As Integer = 1) As Integer  begin:  If (n = 0) Then        '' end condition    Return result  Else                   '' iteration loop    result = result * n  '' iterative accumulation    n = n - 1    Goto begin           '' iterative jump  End IfEnd Function`

Finally it is better to avoid the 'If ... Goto ... End If' instructions by using for example a 'While ... Wend' block instead, and the added 'result' parameter can be transformed into a local variable:

Code: Select all

`Function  betterTranslationToIterativeFactorial (Byval n As Integer) As Integer  Dim As Integer result = 1  While Not (n = 0)          '' end condition of iterative loop    result = result * n      '' iterative accumulation    n = n - 1  Wend  Return resultEnd Function`
2. Similar transformation steps for the simple "reverse string" recursive function following:

Code: Select all

`Function recursiveReverse (Byval s As String) As String  If (s = "") Then                                   '' end condition    Return s  Else                                               '' recursion loop    Return recursiveReverse(Mid(s, 2)) & Left(s, 1)  '' recursive call  End IfEnd Function`

Code: Select all

`Function tailRecursiveReverse (Byval s As String, Byval cumul As String = "") As String  If (s = "") Then                                              '' end condition    Return cumul  Else                                                          '' recursion loop    Return tailRecursiveReverse(Mid(s, 2), Left(s, 1) & cumul)  '' tail recursive call  End IfEnd Function`
Note: As the "&" operator (string concatenation) is not a symmetric operator ((a & b) <> (b & a), while (x * y) = (y * x) like previously), the two operand order must to be reversed when pushing context on execution stack instead of before when popping context from execution stack.

Code: Select all

`Function explicitTailRecursiveReverse (Byval s As String, Byval cumul As String = "") As String  If (s = "") Then                                 '' end condition    Return cumul  Else                                             '' recursion loop    cumul = Left(s, 1) & cumul    s = Mid(s, 2)    Return explicitTailRecursiveReverse(s, cumul)  '' tail recursive call  End IfEnd Function`

Code: Select all

`Function translationToIterativeReverse (Byval s As String, Byval cumul As String = "") As String  begin:  If (s = "") Then              '' end condition    Return cumul  Else                          '' iteration loop    cumul = Left(s, 1) & cumul  '' iterative accumulation    s = Mid(s, 2)    Goto begin                  '' iterative jump  End IfEnd Function`

Code: Select all

`Function betterTranslationToIterativeReverse (Byval s As String) As String  Dim As String cumul = ""  While Not (s = "")            '' end condition of iterative loop    cumul = Left(s, 1) & cumul  '' iterative accumulation    s = Mid(s, 2)  Wend  Return cumulEnd Function`
3. As less simple example, the "Fibonacci series" non-tail recursive function:
Sometimes, the transformation to a tail recursive function is less obvious.
The code body of the recursive function is defined by using the recursive definition of the Fibonacci series:
Case (n = 0) : F(0) = 0
Case (n = 1) : F(1) = 1
Case (n > 1) : F(n) = F(n-1) + F(n-2)
The first two lines allow to determine the end condition: 'If n = 0 Or n = 1 Then Return n'
The third line allows to determine the statement syntax which calls the function itself: 'Return F(n - 1) + F(n - 2)'

Non-tail recursive form code:

Code: Select all

`Function recursiveFibonacci (Byval n As Uinteger) As Longint  If n = 0 Or n = 1 then                                          '' end condition    Return n  Else                                                            '' recursion loop    Return recursiveFibonacci(n - 1) + recursiveFibonacci(n - 2)  '' recursive call  End IfEnd Function`

The execution time duration for the highest values becomes no more negligible.
Indeed, to compute F(n), there are 2^(n-1) calls: about one milliard for n=31.

Try to make the recursive algorithm linear, using a recursive function which have 2 other parameters corresponding to the previous value and the last value of the series, let f(n, a, b).
We obtain:
Case (n = 1): a = F(0) = 0, b = F(1) = 1
Case (n-1): a = F(n-2), b = F(n-1)
Case (n): F(n-1) = b, F(n) = F(n-1) + F(n-2) = a + b

Consequently, for this new function f(n, a, b), the recursive call becomes f(n-1, b, a+b), and there are only (n-1) calls.

Tail recursive form code:

Code: Select all

`Function tailRecursiveFibonacci (Byval n As Uinteger, Byval a As Uinteger = 0, Byval b As Uinteger = 1) As Longint  If n <= 1 Then                                    '' end condition    Return b * n  Else                                              '' recursion loop    Return tailRecursiveFibonacci(n - 1, b, a + b)  '' tail recursive call  End IfEnd Function`

Then, similar transformations as previously in order to obtain the iterative form:

Code: Select all

`Function explicitTailRecursiveFibonacci (Byval n As Uinteger, Byval a As Uinteger = 0, Byval b As Uinteger = 1) As Longint  If n <= 1 Then                                    '' end condition    Return b * n  Else                                              '' recursion loop    n = n - 1    Swap a, b    b = b + a    Return explicitTailRecursiveFibonacci(n, a, b)  '' tail recursive call  End IfEnd Function`

Code: Select all

`Function translationToIterativeFibonacci (Byval n As Uinteger, Byval a As Uinteger = 0, Byval b As Uinteger = 1) As Longint  begin:  If n <= 1 Then  '' end condition    Return b * n  Else            '' iteration loopp    n = n - 1    Swap a, b    b = b + a    Goto begin    '' iterative jump  End IfEnd Function`

Code: Select all

`Function betterTranslationToIterativeFibonacci (Byval n As Uinteger) As Longint  Dim As Uinteger a = 0, b = 1  While Not (n <= 1)  '' end condition of iterative loop    n = n - 1    Swap a, b    b = b + a  Wend  Return b * nEnd Function`
2.2) Replace Non-Tail Recursion with more Complex Iteration
The recursive procedure is a non-tail recursive procedure if there is at least one recursive call followed by at least one instruction.
A non-tail recursion cannot be normally transformed into a simple iteration, or it could have been transformed already into tail recursion.

To avoid limitation due to the execution stack size, a non-tail recursive algorithm can always (more or less easily) be replaced by an iterative algorithm, by pushing the parameters that would normally be passed to the recursive procedure onto an own storage stack. In fact, the execution stack is replaced by a user stack (less limited in size).

In the following examples, the below user stack macro (compatible with any datatype) is used:

Code: Select all

`'' save as file: "DynamicUserStackTypeCreateMacro.bi"#macro DynamicUserStackTypeCreate(typename, datatype)  Type typename    Public:      Declare Constructor ()                       '' pre-allocating user stack memory      Declare Property push (Byref i As datatype)  '' pushing on the user stack      Declare Property pop () Byref As datatype    '' popping from the user stack      Declare Property used () As Integer          '' outputting number of used elements in the user stack      Declare Property allocated () As Integer     '' outputting number of allocated elements in the user stack      Declare Destructor ()                        '' deallocating user stack memory    Private:      Dim As datatype ae (Any)  '' array of elements      Dim As Integer nue        '' number of used elements      Dim As Integer nae        '' number of allocated elements      Dim As Integer nae0       '' minimum number of allocated elements  End Type  Constructor typename ()    This.nae0 = 2^Int(Log(1024 * 1024 / Sizeof(datatype)) / Log(2) + 1) '' only a power of 2 (1 MB < stack memory < 2 MB here)    This.nue = 0    This.nae = This.nae0    Redim This.ae(This.nae - 1)                                         '' pre-allocating user stack memory  End constructor  Property typename.push (Byref i As datatype)  '' pushing on the user stack    This.nue += 1    If This.nue > This.nae0 And This.nae < This.nue * 2 Then      This.nae *= 2      Redim Preserve This.ae(This.nae - 1)  '' allocating user stack memory for double used elements at least    End If    This.ae(This.nue - 1) = i  End Property  Property typename.pop () Byref As datatype  '' popping from the user stack    If This.nue > 0 Then      Property = This.ae(This.nue - 1)      This.nue -= 1      If This.nue > This.nae0 And This.nae > This.nue * 2 Then        This.nae \= 2        Redim Preserve This.ae(This.nae - 1)  '' allocating user stack memory for double used elements at more      End If    Else      Static As datatype d      dim As datatype d0      d = d0      Property = d      Assertwarn(This.nue > 0)  '' warning if popping while empty user stack and debug mode (-g compiler option)    End If  End Property  Property typename.used () As Integer  '' outputting number of used elements in the user stack    Property = This.nue  End property  Property typename.allocated () As Integer  '' outputting number of allocated elements in the user stack    Property = This.nae  End property  Destructor typename  '' deallocating user stack memory    This.nue = 0    This.nae = 0    Erase This.ae  '' deallocating user stack memory  End destructor#endmacro`

2.2.1) Translation Quite Simple from Final Recursive Procedure (non-tail) to Iterative Procedure
A non-tail recursive procedure is final when the recursive call(s) is(are) placed at the end of executed code (no executable instruction line after and between for several recursive calls).

In the 3 following examples, the transformation of a recursive procedure into an iterative procedure is quite simple because the recursive calls are always at the end of executed code block, and without order constraints:
- make the procedure parameters (and the return value for a function) as local ones,
- push the initial parameter values in the user stack,
- enter in a While ... Wend loop to empty the user stack:
- pull the variables from the user stack,
- process the variables similarly to the recursive procedure body,
- accumulate the "return" variable for a recursive function (the final value will be returned at function body end),
- replace the recursive calls by pushing the corresponding variables on the user stack,
1. First example (for console window): Computation of the combination coefficients nCp (binomial coefficients calculation) and display of the Pascal's triangle:
The first function 'recursiveCombination' is the recursive form (not a tail recursion because there are two recursive calls with summation in the last active statement).
The second function 'translationToIterativeCombinationStack' is the iterative form using an own stack.

In the two functions, a similar structure is conserved to enlighten the conversion method.
From recursive function to iterative stacking function:
- ahead, declaration of 1 local variable for the accumulator,
- pushing the two initial parameters values in the user stack,
- entering in the While ... Wend loop to empty the user stack,
- pulling parameters from the user stack,
- 'Return 1' is replaced by 'cumul = cumul + 1',
- 'Return recursiveCombination(n - 1, p) + recursiveCombination(n - 1, p - 1)' is replaced by 'S.push = n - 1 : S.push = p' and 'S.push = n - 1 : S.push = p - 1'.

Code: Select all

`Function recursiveCombination (Byval n As Uinteger, Byval p As Uinteger) As Longint  If p = 0 Or p = n then    Return 1  Else    Return recursiveCombination(n - 1, p) + recursiveCombination(n - 1, p - 1)  End IfEnd Function'---------------------------------------------------------------------------#Include "DynamicUserStackTypeCreateMacro.bi"DynamicUserStackTypeCreate(DynamicUserStackTypeForUinteger, Uinteger)Function translationToIterativeCombinationStack (Byval n As Uinteger, Byval p As Uinteger) As Longint  Dim cumul As Longint = 0  Dim As DynamicUserStackTypeForUinteger S  S.push = n : S.push = p  While S.used > 0    p = S.pop : n = S.pop    If p = 0 Or p = n then      cumul = cumul + 1    Else      S.push = n - 1 : S.push = p      S.push = n - 1 : S.push = p - 1    End If  Wend  Return cumulEnd Function'---------------------------------------------------------------------------Sub Display(Byval Combination As Function (Byval n As Uinteger, Byval p As Uinteger) As Longint, Byval n As Integer)  For I As Uinteger = 0 To n    For J As Uinteger = 0 To I      Locate , 6 * J + 3 * (n - I) + 3      Print Combination(I, J);    Next J    Print  Next IEnd Sub'---------------------------------------------------------------------------Print " recursion:";Display(@recursiveCombination, 12)PrintPrintPrint " iteration with own storage stack:";Display(@translationToIterativeCombinationStack, 12)Sleep`
2. Second example (for graphics window), using a non-tail recursive subroutine (recursive drawing of circles):
Similar transformation steps:

Code: Select all

`Sub recursiveCircle (Byval x As Integer, Byval y As Integer, Byval r As Integer)  Circle (x, y), r  If r > 16 Then    recursiveCircle(x + r / 2, y, r / 2)    recursiveCircle(x - r / 2, y, r / 2)    recursiveCircle(x, y + r / 2, r / 2)    recursiveCircle(x, y - r / 2, r / 2)  End IfEnd Sub'---------------------------------------------------------------------------#Include "DynamicUserStackTypeCreateMacro.bi"DynamicUserStackTypeCreate(DynamicUserStackTypeForInteger, Integer)Sub recursiveToIterativeCircleStack (Byval x As Integer, Byval y As Integer, Byval r As Integer)  Dim As DynamicUserStackTypeForInteger S  S.push = x : S.push = y : S.push = r  Do While S.used > 0    r = S.pop : y = S.pop : x = S.pop    Circle (x, y), r    If r > 16 Then      S.push = x + r / 2 : S.push = y : S.push = r / 2      S.push = x - r / 2 : S.push = y : S.push = r / 2      S.push = x : S.push = y + r / 2 : S.push = r / 2      S.push = x : S.push = y - r / 2 : S.push = r / 2    End If  LoopEnd Sub'---------------------------------------------------------------------------Screen 12Locate 2, 2Print "recursion:"recursiveCircle(160, 160, 150)Locate 10, 47Print "iteration with own storage stack:"recursiveToIterativeCircleStack(480, 320, 150)Sleep`
3. Third example (for console window), using a non-tail recursive subroutine (Quick Sort algorithm):
Similar transformation steps:

Code: Select all

`Dim shared As Ubyte t(99)Sub recursiveQuicksort (Byval L As Integer, Byval R As Integer)  Dim As Integer pivot = L, I = L, J = R  Do    If t(I) >= t(J) then      Swap t(I), t(J)      pivot = L + R - pivot    End If    If pivot = L then      J = J - 1    Else      I = I + 1    End If  Loop Until I = J  If L < I - 1 Then    recursiveQuicksort(L, I - 1)  End If  If R > J + 1 Then    recursiveQuicksort(J + 1, R)  End IfEnd Sub#Include "DynamicUserStackTypeCreateMacro.bi"DynamicUserStackTypeCreate(DynamicUserStackTypeForInteger, Integer)Sub translationToIteraticeQuicksortStack (Byval L As Integer, Byval R As Integer)  Dim As DynamicUserStackTypeForInteger S  S.push = L : S.push = R  While S.used > 0    R = S.pop : L = S.pop    Dim As Integer pivot = L, I = L, J = R    Do      If t(I) >= t(J) then        Swap t(I), t(J)        pivot = L + R - pivot      End If      If pivot = L then        J = J - 1      Else        I = I + 1      End If    Loop Until I = J    If L < I - 1 Then      S.push = L : S.push = I - 1    End If    If R > J + 1 Then      S.push = J + 1 : S.push = R    End If  WendEnd SubRandomizeFor I As Integer = Lbound(t) To Ubound(t)  t(i) = Int(Rnd * 256)Next IPrint "raw memory:"For K As Integer = Lbound(t) To Ubound(t)  Print Using "####"; t(K);Next KPrintrecursiveQuicksort(Lbound(t), Ubound(t))Print "sorted memory by recursion:"For K As Integer = Lbound(t) To Ubound(t)  Print Using "####"; t(K);Next KPrintPrintRandomizeFor I As Integer = Lbound(t) To Ubound(t)  t(i) = Int(Rnd * 256)Next IPrint "raw memory:"For K As Integer = Lbound(t) To Ubound(t)  Print Using "####"; t(K);Next KPrinttranslationToIteraticeQuicksortStack(Lbound(t), Ubound(t))Print "sorted memory by iteration with stack:"For K As Integer = Lbound(t) To Ubound(t)  Print Using "####"; t(K);Next KPrintSleep`
2.2.2) Translation Little More Complex from Non-Final Recursive Procedure to Iterative Procedure
For theses examples, the transformation of the non-final recursive procedure into an iterative procedure is a little more complex because the recursive call(s) is(are) not placed at the end of executed code (see the "final" definition at paragraph 2.2.1).

The general method used hereafter is to first transform original recursive procedure into a "final" recursive procedure where the recursive call(s) is(are) now placed at the end of executed code block (no executable instruction line between or after).

1. First example (for console window), using a non-tail recursive subroutine (tower of Hanoi algorithm):
For this example, the two recursive calls are at the end of executed code block but separated by an instruction line and there is an order constraint.
In the two functions, a similar structure is conserved to enlighten the conversion method.
From recursive function to iterative stacking function:
- the first step consists in removing the instruction line between the two recursive calls by adding its equivalent at top of the recursive code body (2 parameters ares added to the procedure to pass the corresponding useful data),
- then the process of translation to iterative form is similar to the previous examples (using a own storage stack) but reversing the order of the 2 recursive calls when pushing on the storage stack.

Code: Select all

`Sub recursiveHanoi (Byval n As Integer, Byval departure As String, Byval middle As String, Byval arrival As String)  If n > 0 Then    recursiveHanoi(n - 1, departure, arrival, middle)    Print "  move one disk from " & departure & " to " & arrival    recursiveHanoi(n -1 , middle, departure, arrival)  End IfEnd SubSub finalRecursiveHanoi (Byval n As Integer, Byval departure As String, Byval middle As String, Byval arrival As String, Byval dep As String = "", Byval arr As String = "")  If dep <> "" Then Print "  move one disk from " & dep & " to " & arr  If n > 0 Then    finalRecursiveHanoi(n - 1, departure, arrival, middle, "")    finalRecursiveHanoi(n - 1, middle, departure, arrival, departure, arrival)  End IfEnd Sub#Include "DynamicUserStackTypeCreateMacro.bi"DynamicUserStackTypeCreate(DynamicUserStackTypeForString, String)Sub translationToIterativeHanoi (Byval n As Integer, Byval departure As String, Byval middle As String, Byval arrival As String)  Dim As String dep = "", arr = ""  Dim As DynamicUserStackTypeForString S  S.push = Str(n) : S.push = departure : S.push = middle : S.push = arrival : S.push = dep : S.push = arr  While S.used > 0    arr = S.pop : dep = S.pop : arrival = S.pop : middle = S.pop : departure = S.pop : n = Val(S.pop)    If dep <> "" Then Print "  move one disk from " & dep & " to " & arr    If n > 0 Then      S.push = Str(n - 1) : S.push = middle : S.push = departure : S.push = arrival : S.push = departure : S.push = arrival      S.push = Str(n - 1) : S.push = departure : S.push = arrival : S.push = middle : S.push = "" : S.push = ""    End If  WendEnd SubPrint "recursive tower of Hanoi:"recursiveHanoi(3, "A", "B", "C")PrintPrint "final recursive tower of Hanoi:"finalRecursiveHanoi(3, "A", "B", "C")PrintPrint "iterative tower of Hanoi:"translationToIterativeHanoi(3, "A", "B", "C")PrintSleep`
2. Second example (for console window), using a non-tail recursive subroutine (counting-down from n, then re-counting up to n):
For this example, the recursive call is followed by an instruction line before the end of executed code block.
In the two functions, a similar structure is conserved to enlighten the conversion method.
From recursive function to iterative stacking function:
- the first step consists in replacing the instruction line at the end of executed code block by a new recursive call (a parameter is added to the procedure to pass the corresponding useful data),
- an equivalent instruction line is added at top of the recursive code body (using the passed data), executed in this case instead of the normal code,
- then the process of translation to iterative form is similar to the previous example (using a own storage stack) and reversing the order of the 2 recursive calls when pushing on the storage stack.

Code: Select all

`Sub recursiveCount (Byval n As Integer)  If n >= 0 Then    Print n & " ";    If n = 0 Then Print    recursiveCount(n - 1)    Print n & " ";  End IfEnd SubSub finalRecursiveCount (Byval n As Integer, Byval recount As String = "")  If recount <> "" Then    Print recount & " ";  Else    If n >= 0 Then      Print n & " ";      If n = 0 Then Print      finalRecursiveCount(n - 1, "")      finalRecursiveCount(n - 1, Str(n))    End If  End IfEnd Sub#Include "DynamicUserStackTypeCreateMacro.bi"DynamicUserStackTypeCreate(DynamicUserStackTypeForString, String)Sub translationToIterativeCount (Byval n As Integer)  Dim As String recount = ""  Dim As DynamicUserStackTypeForString S  S.push = Str(n) : S.push = recount  While S.used > 0    recount = S.pop : n = Val(S.pop)  If recount <> "" Then    Print recount & " ";  Else    If n >= 0 Then      Print n & " ";      If n = 0 Then Print      S.push = Str(n - 1) : S.push = Str(n)      S.push = Str(n - 1) : S.push = ""    End If  End If  WendEnd SubPrint "recursive counting-down then re-counting:"recursiveCount(9)PrintPrintPrint "final recursive counting-down then re-counting:"finalRecursiveCount(9)PrintPrintPrint "iterative counting-down then re-counting:"translationToIterativeCount(9)PrintPrintSleep`
2.2.3) Translation from Other Non-Obvious Recursive Procedure to Iterative Procedure
Two other cases of translation from recursion to iteration are presented here by means of simple examples:
- for mutual recursion,
- for nested recursion.
1. Example using mutual recursive functions ('even()' and 'odd()' functions):
From mutual recursive procedures to iterative stacking procedures (for the general case):
- the first step consists in transforming the recursive procedures into "final" recursive procedures (see the "final" definition at paragraph 2.2.1),
- then, the method is similar than that already described, with besides an additional parameter (an index) which is also pushed on the user stack in order to select the right code body to execute when pulling data from the stack,
- therefore, each iterative procedure contains the translation (for stacking) of all code bodies from the recursive procedures.
In this following examples, the simple mutual recursive functions are here processed as in the general case (other very simple iterative solutions exist):

Code: Select all

`Declare Function recursiveIsEven(Byval n As Integer) As BooleanDeclare Function recursiveIsOdd(Byval n As Integer) As BooleanFunction recursiveIsEven(Byval n As Integer) As Boolean  If n = 0 Then    Return True  Else    Return recursiveIsOdd(n - 1)  End IfEnd FunctionFunction recursiveIsOdd(Byval n As Integer) As Boolean  If n = 0 Then    Return False  Else    Return recursiveIsEven(n - 1)  End IfEnd Function#Include "DynamicUserStackTypeCreateMacro.bi"DynamicUserStackTypeCreate(DynamicUserStackTypeForInteger, Integer)Function iterativeIsEven(Byval n As Integer) As Boolean  Dim As Integer i = 1  Dim As DynamicUserStackTypeForInteger S  S.push = n : S.push = i  While S.used > 0    i = S.pop : n = S.pop    If i = 1 Then      If n = 0 Then        Return True      Else        S.push = n - 1 : S.push = 2      End If    Elseif i = 2 Then      If n = 0 Then        Return False      Else        S.push = n - 1 : S.push = 1      End If    End If  WendEnd FunctionFunction iterativeIsOdd(Byval n As Integer) As Boolean  Dim As Integer i = 2  Dim As DynamicUserStackTypeForInteger S  S.push = n : S.push = i  While S.used > 0    i = S.pop : n = S.pop    If i = 1 Then      If n = 0 Then        Return True      Else        S.push = n - 1 : S.push = 2      End If    Elseif i = 2 Then      If n = 0 Then        Return False      Else        S.push = n - 1 : S.push = 1      End If    End If  WendEnd FunctionPrint recursiveIsEven(16), recursiveIsOdd(16)Print recursiveIsEven(17), recursiveIsOdd(17)PrintPrint iterativeIsEven(16), iterativeIsOdd(16)Print iterativeIsEven(17), iterativeIsOdd(17)PrintSleep`
2. Example using nested recursive function ('Ackermann()' function):
From nested recursive function to iterative stacking function:
- use 2 independent storage stacks, one for the first parameter "m" and another for the second parameter "n" of the function, because of the nested call on one parameter,
- 'Return expression' is transformed into a pushing the expression on the stack dedicated to the parameter where the nesting call is,
- therefore a 'Return' of data popping from the same stack is added at code end.

Code: Select all

`Function recursiveAckermann (Byval m As Integer, Byval n As Integer) As Integer  If m = 0 Then    Return n + 1  Else    If n = 0 Then      Return recursiveAckermann(m - 1, 1)    Else      Return recursiveAckermann(m - 1, recursiveAckermann(m, n - 1))    End If  End IfEnd Function#Include "DynamicUserStackTypeCreateMacro.bi"DynamicUserStackTypeCreate(DynamicUserStackTypeForInteger, Integer)Function iterativeAckermann (Byval m As Integer, Byval n As Integer) As Integer  Dim As DynamicUserStackTypeForInteger Sm, Sn  Sm.push = m : Sn.push = n  While Sm.used > 0    m = Sm.pop : n = Sn.pop    If m = 0 Then      Sn.push = n + 1                                    ' Return n + 1 (and because of nested call)    Else      If n = 0 Then        Sm.push = m - 1 : Sn.push = 1                    ' Return Ackermann(m - 1, 1)      Else        Sm.push = m - 1 : Sm.push = m : Sn.push = n - 1  ' Return Ackermann(m - 1, Ackermann(m, n - 1))      End If    End If  Wend  Return Sn.pop                                          ' (because of Sn.push = n + 1)End FunctionPrint recursiveAckermann(3, 0), recursiveAckermann(3, 1), recursiveAckermann(3, 2), recursiveAckermann(3, 3), recursiveAckermann(3, 4)Print iterativeAckermann(3, 0), iterativeAckermann(3, 1), iterativeAckermann(3, 2), iterativeAckermann(3, 3), iterativeAckermann(3, 4)Sleep`
badidea
Posts: 1295
Joined: May 24, 2007 22:10
Location: The Netherlands

### Re: How to Replace Any Recursion with Simple Iteration or Unlimited Iteration with its Own Stack, in FB

Paint, using your DynamicUserStackTypeCreateMacro.bi (not optimised for speed).
Code updated:

Code: Select all

`Const As Single PI = 2 * Atan2(1,0)Const As Ulong WHITE = &h00ffffffConst As Ulong RED = &h00dd0000Const As Ulong GREEN = &h0000aa00Const As Ulong BLUE = &h000000ddSub recursivePaint(x As Long, y As Long, fillColor As Long, borderColor As Long)   If Point(x, y) = fillColor Or Point(x, y) = borderColor Then      Exit Sub   Else      Pset(x, y), fillColor      'sleep 1,1 'enable for slow animation      recursivePaint(x + 1, y, fillColor, borderColor)      recursivePaint(x, y + 1, fillColor, borderColor)      recursivePaint(x - 1, y, fillColor, borderColor)      recursivePaint(x, y - 1, fillColor, borderColor)   End IfEnd Sub#Include "DynamicUserStackTypeCreateMacro.bi"DynamicUserStackTypeCreate(DynamicUserStackTypeForLong, Long)Sub recursiveToIterativePaint(x As Long, y As Long, fillColor As Long, borderColor As Long)   Dim As DynamicUserStackTypeForLong S   S.push = x : S.push = y   Do While S.used > 0      y = S.pop : x = S.pop 'pop in reverse      If Point(x, y) = fillColor Or Point(x, y) = borderColor Then         Continue Do      Else         Pset(x, y), fillColor 'add check         S.push = x + 1 : S.push = y         S.push = x : S.push = y + 1         S.push = x - 1 : S.push = y         S.push = x : S.push = y - 1      End If   LoopEnd SubScreenres 800,600,32'draw a flowerFor a As Single = 0 To PI*2 Step PI/6   Line(400 + Cos(a) * 280, 300 + Sin(a) * 280) - (400 + Cos(a-PI/8) * 150, 300 + Sin(a-PI/8) * 150), WHITE   Line(400 + Cos(a) * 280, 300 + Sin(a) * 280) - (400 + Cos(a+PI/8) * 150, 300 + Sin(a+PI/8) * 150), WHITE   Circle (400, 300), 140 - a * 20, WHITE, a, a + PI * 1.8NextWhile inkey\$ = ""   Paint (400, 300), RED, WHITE   Sleep 200,1   recursivePaint(400, 300, BLUE, WHITE)   Sleep 200,1   recursiveToIterativePaint(400, 300, GREEN, WHITE)   Sleep 200,1Wend Print "Done"`

Ulong can be another integer. I was pushing and popping the colors also initially. This was not needed of course.

I should try this on my Pentominoes solver or my Checkers / draughts computer

Note: Some closing quotes (") missing in your 'Hanoi towers'.
Last edited by badidea on Sep 22, 2018 21:54, edited 2 times in total.
fxm
Posts: 8907
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

### Re: How to Replace Any Recursion with Simple Iteration or Unlimited Iteration with its Own Stack, in FB

badidea wrote:Note: Some closing quotes (") missing in your 'Hanoi towers'.
Thanks (corrected now).

badidea wrote:Paint, using your DynamicUserStackTypeCreateMacro.bi (not optimised for speed)
In your code, you do not have to define local variables 'xs' and 'ys' because the variables 'x' and 'y' are passed by value.
badidea
Posts: 1295
Joined: May 24, 2007 22:10
Location: The Netherlands

### Re: How to Replace Any Recursion with Simple Iteration or Unlimited Iteration with its Own Stack, in FB

fxm wrote:In your code, you do not have to define local variables 'xs' and 'ys' because the variables 'x' and 'y' are passed by value.
Code updated.
paul doe
Posts: 912
Joined: Jul 25, 2017 17:22
Location: Argentina

### Re: How to Replace Any Recursion with Simple Iteration or Unlimited Iteration with its Own Stack, in FB

Really nice and comprehensive work, fxm. Well done!
dodicat
Posts: 5700
Joined: Jan 10, 2006 20:30
Location: Scotland

### Re: How to Replace Any Recursion with Simple Iteration or Unlimited Iteration with its Own Stack, in FB

Thanks fxm
Powerbasic had a recursive hanoi.
Here is a translation.

Code: Select all

` '============================================================================='  This  program demostrates a recursive version of the popular "Towers'  of Hanoi" game.''  In order to run this program do the following:                           ³'    1. Load PowerBASIC by typing PB at the DOS prompt.'    2. Load the file HANOI.BAS from the Load option of the File'       pulldown menu.'    3. Compile and run the program by pressing F9.'=============================================================================Screen 9'\$STACK 32766 ' allocate plenty of stack space since it's a recursive programDeclare Sub DisplayMoveConst X  = 1   ' named constants used for indexing and screen positioningConst Y  = 0Const PromptLine = 24   ' named constant indicating line for all user promptsConst MaxDisks   = 13   ' named constant indicating maximum number of disksConst CursorOff  = 0Dim Shared RecursionDepth As Integer' global variable declarationsDim Shared NumberOfDisks(1 To MaxDisks + 1) As Integer, SourceTower(1 To MaxDisks + 1)As IntegerDim Shared TargetTower(1 To MaxDisks + 1)As Integer, Disk(1 To MaxDisks + 1)As StringDim Shared DisksPosition(MaxDisks,1)As Integer, TowerHeight(1 To 3)As IntegerDim Shared As Integer NumberOfMoves = 0               ' used to keep track of number of moves madeDim Shared As Integer BottomLine    = 24              ' used to indicate bottom line of displayDim Shared As Integer TowerBase     = 2Sub Init   ' This procedure is used to initialize the screen and get the number    ' of disks to use.    Dim c As Integer    Color 7, 0                              ' initialize screen color    Cls    Color 4, 0    Locate 1, 26, CursorOff    Print "TOWERS OF HANOI"                 ' display the program banner    Color 6, 0    Locate PromptLine, X, CursorOff    Print "Number of Disks (1 TO " + Str(MaxDisks) +  ") ";    Do   ' get the number of disks from the user        Locate PromptLine, Len("Number of Disks (1 TO " + Str(MaxDisks) +  ") ") + 1, CursorOff        Input NumberOfDisks(1)        If NumberOfDisks(1) > MaxDisks Then Beep    Loop Until NumberOfDisks(1) <= MaxDisks    TowerBase = TowerBase + NumberOfDisks(1)    Color 7, 0    Locate PromptLine, X, CursorOff    Print Space(79)                        ' clear prompt lineEnd Sub  ' end procedure InitSub DisplayGameScreen  ' This procedure displays a message on the screen    Locate 1, 26,CursorOff              ' position the cursor and turn it on    Color 4, 0                            ' set the display color    Print "TOWERS OF HANOI FOR"; NumberOfDisks(1); "DISKS"    Locate TowerBase + 1, X, CursorOff   ' position the cursor    Color 1, 0                              ' set the display color    Print String(80,176);                  ' display a bar on the screen    Color 7,0                               ' set the display colorEnd Sub  ' end procedure DisplayGameScreenSub MakeMoves(Byref  NumMoves As Integer)        RecursionDepth=RecursionDepth+1    ' check if we should exit routine    If NumberOfDisks(RecursionDepth) = 0 Then                RecursionDepth=RecursionDepth-1        Exit Sub    End If        NumberOfDisks(RecursionDepth + 1) = NumberOfDisks(RecursionDepth) - 1    SourceTower(RecursionDepth + 1) = SourceTower(RecursionDepth)    TargetTower(RecursionDepth + 1) = 6 - _    SourceTower(RecursionDepth) - TargetTower(RecursionDepth)    MakeMoves(NumMoves)    NumMoves= NumMoves+1        DisplayMove    NumberOfDisks(RecursionDepth + 1) = NumberOfDisks(RecursionDepth) - 1    SourceTower(RecursionDepth + 1) = 6 - _    SourceTower(RecursionDepth) - TargetTower(RecursionDepth)    TargetTower(RecursionDepth + 1) = TargetTower(RecursionDepth)    MakeMoves(NumMoves)    RecursionDepth=RecursionDepth-1    End Sub Sub DisplayMove    sleep 14-NumberOfDisks(1)    Dim column As Integer        If TargetTower(RecursionDepth) = 1 Then        Column = 1    Elseif TargetTower(RecursionDepth) = 2 Then        Column = 27    Elseif TargetTower(RecursionDepth) = 3 Then        Column = 54    End If        ' go to the position of the next disk to move    Locate DisksPosition(NumberOfDisks(RecursionDepth),Y), _    DisksPosition(NumberOfDisks(RecursionDepth),X), CursorOff    Color 7,0    Print Space(26)      ' erase current disk        ' increment the height of the tower the disk is moving to        TowerHeight(SourceTower(RecursionDepth))=TowerHeight(SourceTower(RecursionDepth))+1    ' position cursor at top of destination tower    Locate TowerHeight(TargetTower(RecursionDepth)), Column, CursorOff        ' get the color    Color NumberOfDisks(RecursionDepth) Mod 14 + 1,0    Print Disk(NumberOfDisks(RecursionDepth));   ' display the disk        Color 7,0        ' update the current position of this disk    DisksPosition(NumberOfDisks(RecursionDepth),Y) = _    TowerHeight(TargetTower(RecursionDepth))    DisksPosition(NumberOfDisks(RecursionDepth),X) = Column        ' decrement the height of the tower the disk came from    TowerHeight(TargetTower(RecursionDepth)) = _    TowerHeight(TargetTower(RecursionDepth)) - 1End Sub ' start of main programInit' initialize the array of disksFor X1 As Integer = 1 To NumberOfDisks(1)        ' for the number of disks    Disk(X1) = String(26,32)  ' fill the array with spaces    Mid(Disk(X1), MaxDisks + 1 - X1, X1 * 2 - 1) = String(30,219)Next X1' display the initial disksDim Top As Integer = TowerBase - NumberOfDisks(1)For X1 As Integer = 1 To NumberOfDisks(1)    DisksPosition(X1,Y) = Top + X1      ' assign row display    DisksPosition(X1,X) = 1              ' assign column display    Locate Top + X1, 1,CursorOff' position cursor    Color X1 Mod 14 + 1,0       ' change color    Print Disk(X1);            ' display the current diskNext X1Sleep 1000DisplayGameScreen         ' display game screenTowerHeight(1) = Top              ' initialize global variablesTowerHeight(2) = TowerBaseTowerHeight(3) = TowerBaseSourceTower(1) = 1TargetTower(1) = 3RecursionDepth = 0Locate 1, 1,CursorOff Print "Start time: " ;Int(Timer)MakeMoves( NumberOfMoves) ' start gameLocate 2, 1,CursorOff Print "Stop time : "; Int(Timer)Locate PromptLine, 26Print "DONE IN "; NumberOfMoves; " MOVES";SleepEnd  ' end of program  `
fxm
Posts: 8907
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

### Re: How to Replace Any Recursion with Simple Iteration or Unlimited Iteration with its Own Stack, in FB

Thanks
Increase the sleep time in DisplayMove() is more demonstrative.
Lost Zergling
Posts: 179
Joined: Dec 02, 2011 22:51
Location: France

### Re: How to Replace Any Recursion with Simple Iteration or Unlimited Iteration with its Own Stack, in FB

Hello fxm. First of all thank you because this post is didactic, clear, precise and neutral. I'm a little 'offtopic', to see but in any case on the recursion. As you may have noticed, in my list manipulation tools I use two competing recursive techniques in 'nodeflat', and I am very interested in the possible tracks to optimize the operation. You have already helped me a lot with the simple idea of ​​a global variable to track the deallocations (it's silly but I just did not think). The typical recursion case I am thinking of is the path of a tree and the recursive (backward) path is initiated by the kinematics of the pointers, in which case it is the tree itself that serves as a user stack (virtually linearized). But since the nodeflat instruction must be able to take place (or not) in a recursion already itself iterated and therefore interrupted (hashstep), then the actually recursive mode allows to have reverse recursion to the request even outside of the hashstep loop, with the same instruction. I do not dare to touch this code, but I have the intuition that it could perhaps be optimized. I have another problem: I introduced a recursion in the hashtag and my tests seem to show a threshold effect impacting overall performance, but it's stealthy: would it come from recursion, a test , the size of the property, I have difficulty to determine it accurately. So far new hashTag is slower than previous, but the reason why is very difficult to identify.
Lost Zergling
Posts: 179
Joined: Dec 02, 2011 22:51
Location: France

### Re: How to Replace Any Recursion with Simple Iteration or Unlimited Iteration with its Own Stack, in FB

@fxm : slowdown fixed - this one wasn't due to a recursive call.
badidea
Posts: 1295
Joined: May 24, 2007 22:10
Location: The Netherlands

### Re: How to Replace Any Recursion with Simple Iteration or Unlimited Iteration with its Own Stack, in FB

I have modified you stack implementation for other purposes, I hope you don't mind.

Code: Select all

`#macro listTypeCreate(list_type, data_type)   type list_type      public:      declare property push(byval value as data_type)      declare property pop() as data_type      declare property size() as integer 'stack size      declare property find(byval value as data_type) as integer      declare property get(index as integer) as data_type      declare destructor()      private:      dim as data_type list(any) 'stack      dim as integer current = 0   end type   'increase list size + add value   property list_type.push(byval value as data_type)      redim preserve list(ubound(list) + 1)      list(ubound(list)) = value   end property   property list_type.pop() as data_type      dim as data_type value      select case ubound(list)      case is > 0         'get value + decrease list size         value = list(ubound(list))         redim preserve list(ubound(list) - 1)      case is = 0         'get value + empty list         value = list(ubound(list))         erase list      case else         'keep uninitialised value      end select      return value   end property   property list_type.size() as integer      return ubound(list) + 1   end property   'find first match   property list_type.find(byval value as data_type) as integer      for i as integer = lbound(list) to ubound(list)         if list(i) = value then return i       next      return -1   end property   property list_type.get(index as integer) as data_type      dim as data_type value      if index >= lbound(list) and index <= ubound(list) then         value = list(index)      end if      return value    end property   destructor list_type      erase list   end destructor#endmacrolistTypeCreate(listTypeUlong, ulong)dim as listTypeUlong listlist.push = 111 'property asignment formatlist.push = 333list.push(333)list.push(555)print "list.size() = "; list.size()?print "list.find(333) = "; list.find(333)print "list.find(555) = "; list.find(555)print "list.find(888) = "; list.find(888)?for i as integer = -1 to list.size() - 1 + 1   print "list.get(" + str(i) + ") = "; list.get(i)next?while list.size() > 0   print "list.pop() = "; list.pop()wend?print "list.size() = "; list.size()`
fxm
Posts: 8907
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

### Re: How to Replace Any Recursion with Simple Iteration or Unlimited Iteration with its Own Stack, in FB

No problem. Everyone has the right to be inspired by code on the forum (like my first version of user stack) and modify it as it sees fit.

Myself, I yesterday modified it, but just to gain speed of execution!
(important when we want to replace the execution stack by its own stack)
See the first post, at the beginning of paragraph 2.2).
marcov
Posts: 2748
Joined: Jun 16, 2005 9:45
Location: Eindhoven, NL
Contact:

### Re: How to Replace Any Recursion with Simple Iteration or Unlimited Iteration with its Own Stack, in FB

This describes auto-recursion, but maybe it would be fun to work out a mutual recusion (or even a more complex one like a recursive descent expression parser) case? I've seen factorials linearized often, but the demonstrations always are for the simpler cases.
fxm
Posts: 8907
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

### Re: How to Replace Any Recursion with Simple Iteration or Unlimited Iteration with its Own Stack, in FB

I think that there is no fundamental problem for mutual recursive procedures.
From mutual recursive procedures to iterative stacking procedures:
- the first step consists in transforming the recursive procedures into "final" recursive procedures (see the "final" definition at paragraph 2.2.2 of my article),
- then, the method is similar than that already described, with besides an additional parameter (an index) which is also pushed on the user stack in order to select the right code body to execute when pulling data from the stack,
- therefore, each iterative procedure contains the translation (for stacking) of all code bodies from the recursive procedures.
Simple "even/odd" functions for example:

Code: Select all

`Declare Function recursiveIsEven(Byval n As Integer) As BooleanDeclare Function recursiveIsOdd(Byval n As Integer) As BooleanFunction recursiveIsEven(Byval n As Integer) As Boolean  If n = 0 Then    Return True  Else    Return recursiveIsOdd(n - 1)  End IfEnd FunctionFunction recursiveIsOdd(Byval n As Integer) As Boolean  If n = 0 Then    Return False  Else    Return recursiveIsEven(n - 1)  End IfEnd Function#Include "DynamicUserStackTypeCreateMacro.bi"DynamicUserStackTypeCreate(DynamicUserStackTypeForInteger, Integer)Function iterativeIsEven(Byval n As Integer) As Boolean  Dim As Integer i = 1  Dim As DynamicUserStackTypeForInteger S  S.push = n : S.push = i  While S.used > 0    i = S.pop : n = S.pop    If i = 1 Then      If n = 0 Then        Return True      Else        S.push = n - 1 : S.push = 2      End If    Elseif i = 2 Then      If n = 0 Then        Return False      Else        S.push = n - 1 : S.push = 1      End If    End If  WendEnd FunctionFunction iterativeIsOdd(Byval n As Integer) As Boolean  Dim As Integer i = 2  Dim As DynamicUserStackTypeForInteger S  S.push = n : S.push = i  While S.used > 0    i = S.pop : n = S.pop    If i = 1 Then      If n = 0 Then        Return True      Else        S.push = n - 1 : S.push = 2      End If    Elseif i = 2 Then      If n = 0 Then        Return False      Else        S.push = n - 1 : S.push = 1      End If    End If  WendEnd FunctionPrint recursiveIsEven(16), recursiveIsOdd(16)Print recursiveIsEven(17), recursiveIsOdd(17)PrintPrint iterativeIsEven(16), iterativeIsOdd(16)Print iterativeIsEven(17), iterativeIsOdd(17)PrintSleep`

But by cons I think that there is a big problem for a nested recursive procedure.
"Ackermann" function for example:

Code: Select all

`Function Ackermann (Byval m As Integer, Byval n As Integer) As Integer  If m = 0 Then    Return n + 1  Else    If n = 0 Then      Return Ackermann(m - 1, 1)    Else      Return Ackermann(m - 1, Ackermann(m, n - 1))    End If  End IfEnd Function`
fxm
Posts: 8907
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

### Re: How to Replace Any Recursion with Simple Iteration or Unlimited Iteration with its Own Stack, in FB

fxm wrote:But by cons I think that there is a big problem for a nested recursive procedure.
"Ackermann" function for example:

In fact, the solution is quite simple:
- use 2 independent storage stacks, one for the first parameter "m" and another for the second parameter "n" of the function, because of the nested call on one parameter,
- 'Return expression' is transformed into a pushing the expression on the stack dedicated to the parameter where the nesting call is,
- therefore a 'Return' of data popping from the same stack is added at code end.

Code: Select all

`Function recursiveAckermann (Byval m As Integer, Byval n As Integer) As Integer  If m = 0 Then    Return n + 1  Else    If n = 0 Then      Return recursiveAckermann(m - 1, 1)    Else      Return recursiveAckermann(m - 1, recursiveAckermann(m, n - 1))    End If  End IfEnd Function#Include "DynamicUserStackTypeCreateMacro.bi"DynamicUserStackTypeCreate(DynamicUserStackTypeForInteger, Integer)Function iterativeAckermann (Byval m As Integer, Byval n As Integer) As Integer  Dim As DynamicUserStackTypeForInteger Sm, Sn  Sm.push = m : Sn.push = n  While Sm.used > 0    m = Sm.pop : n = Sn.pop    If m = 0 Then      Sn.push = n + 1                                    ' Return n + 1 (and because of nested call)    Else      If n = 0 Then        Sm.push = m - 1 : Sn.push = 1                    ' Return Ackermann(m - 1, 1)      Else        Sm.push = m - 1 : Sm.push = m : Sn.push = n - 1  ' Return Ackermann(m - 1, Ackermann(m, n - 1))      End If    End If  Wend  Return Sn.pop                                          ' (because of Sn.push = n + 1)End FunctionPrint recursiveAckermann(3, 0), recursiveAckermann(3, 1), recursiveAckermann(3, 2), recursiveAckermann(3, 3), recursiveAckermann(3, 4)Print iterativeAckermann(3, 0), iterativeAckermann(3, 1), iterativeAckermann(3, 2), iterativeAckermann(3, 3), iterativeAckermann(3, 4)Sleep`
fxm
Posts: 8907
Joined: Apr 22, 2009 12:46
Location: Paris suburbs, FRANCE

### Re: How to Replace Any Recursion with Simple Iteration or Unlimited Iteration with its Own Stack, in FB

Added at the header article these previous two examples of translation from recursion to iteration (for mutual recursion, and for nested recursion) in a last paragraph (2.2.3).

Return to “Documentation”

### Who is online

Users browsing this forum: No registered users and 1 guest