Ok, the original recursive algorithm (that works):
Code:
void solveRecurse(int currentJob)
{
1 char currentJobSched = jobs[currentJob].getSchedule();
2 int jobSize = jobs.size();
3 char getComp;
4
5 if (currentJobSched != '-' && currentJob >= 0)
6 {
7 numOfJobs++;
8 if (numOfJobs > currentBest)
9 {
10 currentBest = numOfJobs;
11 best = jobs;
12 }
13 computers[currentJobSched - 97].addJob(jobs[c4urrentJob].getEnd());
14 }
15 if (currentJob + 1 < jobSize)
16 {
17 for (int i = 0; i < Job::getMachPerJob(); i++)
18 {
19 getComp = jobs[currentJob + 1].getComp(i);
20 if (computers[getComp - 97].isAvailable(jobs[currentJob + 1].getStart()))
21 {
22 jobs[currentJob + 1].setSchedule(getComp);
23 solveRecurse(currentJob + 1);
24 }
25 }
26 jobs[currentJob + 1].setSchedule('-');
27 solveRecurse(currentJob + 1);
28 }
29 if (currentJobSched != '-' && currentJob >= 0)
30 {
31 computers[currentJobSched - 97].removeJob();
32 numOfJobs--;
33 }
}
And here is the speudo code for an iterative implementation of a tail-recursive algorithm:
Code:
//prime the pump
push initial locals
WHILE stack not empty
//this is our "recursive" entry point, peek the TOS to get locals
...
//to mimic a recursive call, push and continue
...
//to mimic a "return", pop and continue
ENDWHILE
The problem is that the recursive algorithm is not tail recursive. Namely, both recursive calls on lines 23 and 27 both need to do additional work when the recursive calls return.
So my idea is to expand the functionality at the top of the WHILE to being not only the recursive entry point, but also the "do post recursive call work".
To accoplish this, each stack frame will also keep up with the following state information:
- in recursion site 1 call (line 23)
- in recursion site 2 call (line 27)
Then, to mimic a recusive call on lines 23 and 27 you will:
Code:
set state in current frame (TOS), "in recursion site [1,2] call"
push frame for new recursive call
continue
The WHILE loop will then look something like:
Code:
WHILE stack not empty
peek TOS to get current frame
IF in recursion site 1 call
do work that follows site 1 call
ELSE IF in recursion site 2 call
do work that follows site 2 call
ELSE
do work for a "fresh" call
ENDIF
ENDWHILE
As is, this will have a LOT of redundant code since "work after site 1" includes "work after site 2", and the final ELSE contains all that work.........if there were ever a reason to use goto's THIS IS IT! Its a rare opportunity indeed, lets relish it
So we can keep the original form and just place some labels right after the "continue" that represents the recursive call mimic for lines 23 and 27. The WHILE loop then looks like:
Code:
WHILE stack not empty
peek TOS to get current frame
IF in recursion site 1 call
goto post_site_1_call
ELSE IF in recursion site 2 call
goto post_site_2_call
ENDIF
do work for a "fresh" call
ENDWHILE
What do you think?
gg