Friday, October 28, 2016

Recursions on steroids!

Below is the current recursion call, I want to make it a generator.  hat is the stack used for? Carry the accumulated index fount as the operator descends he graph.  The other call parameters are for the operator, and are static pointers.  So I am going to replace the recursive call with a pop and push on a list, and carry the list pointer rather then the id itself. Wrap the whole routine below in a while loop which says 'while id list is not empty, keep doing this'.

Modified, it looks like (untested):

def Recurse(fun,arglist)
 idlist=[]
 idlist.push(0)
 while idlist.len() > 0 :
  id = idlist.pop()
  self = G.GET(id)
  end = id + self.count 
 if fun(self,id,arglist) == CONTINUE :  
  id = id + 1 # skip the anchor
  if id  < end  and (self.return_val == CONTINUE) :
  push(id)
  else :
  if self.return_val == BLOCK : self.return_val = CONTINUE

 Look, no function call back to recurse!  Does it help much?  Where we have a short structure, and each 'node' mostly contains a long list of singletons,then this does not help because we skip the recurse on block count =1.  But it doesn't hurt much.

No comments: