Recursion & Paging

stevenmu

More out of curiosity than anything else, I'm just wondering if anyone has any ideas on paging within recursive algorithms, or if it's even possible. (what I'm sure I'll end up doing is just building up a list first to iterate through later)

Specifically I'm trying to write a little .Net utility for printing a treeview. The .Net printing model basically is that you create a PrintingDocument object, set a few page and printer parameters and then call Print(). This fires the PagePrint event, where you render your stuff to it's graphics object (or graphics context for java heads iirc). Roughly speaking

private sub PagePrint(sender as object, ev as PrintDocument.Printargs) handles PrintDocument.PagePrint
   For Each rootnode
       ev.graphics.drawstring(rootNode.text)
       
       renderChildren(rootnode, ev)
   next

   ev.Morepages = ? ' true if more pages to do or false if last page done
end sub

private sub renderChildren(parent as treenode, ev as PrintDocument.Printargs)
   ev.graphics.drawstring(parent.text)

   For Each childnode in parent    
       renderChildren(parent, ev)
   next

end sub

I can figure out how many nodes I can fit per page, and keep track of how many I've rendered, so what I need to do is find someway to 'break out' of the recursive loop when I've filled a page, returning to Sub PagePrint, set MorePages = true, which means PagePrint will be called again, and then the really tricky part, when PagePrint is called again for the next page, return to where I was in the recursive loop and carry on.

I could, I think do it by holding the next line number to be rendered somewhere, and start the recursive loop again, comparing my current line number against it untill it's reached and then start rendering again, but that strikes me as really inelegant, maybe I'm just a perfectionist.

mewso

Why don't you just have a winform level counter variable. Increment it on every call to the renderchildren and exit out of it when the counter reachers a certain number, resetting it to 1.

stevenmu

As I understand what you're saying, it'll let me exit the loop to finish the page, but when it comes to the next page I need to carry on where I left off before.

theexis

You could consider splitting your logic into 2; e.g. 1 class that is the data source (stream) and the printing code. The PrintCode calls "GetNextNode" until no nodes are left. the data source keeps track of node level and position in the data.

mewso

Actually my suggestion wouldn't work on second thoughts. A bit more complex than I thought.

rsynnott

I was sooo sure this thread was going to involve RISC.... and then DISAPPOINTMENT.

robindch

Personally, I'd rewrite it as a tail recursive function and your problems will disappear immediately. Recursion, while cute, does not lead itself to maintainable code...

theexis

robindch wrote:

Personally, I'd rewrite it as a tail recursive function and your problems will disappear immediately. Recursion, while cute, does not lead itself to maintainable code...

Unless you're in Prolog then you don't have a lot of options

rsynnott

theexis wrote:

Unless you're in Prolog then you don't have a lot of options

Indeed; EVERY problem must be solved with recursion, unless you're a deviant, and use the '/=' operator. It is my theory that the inventors of prolog simply had lots of shares in Sun, or another company that made processors with lots of overlapping register files.

stevenmu

lol, I always thought prolog was invented by some sick, twisted lecturer to scare off 3rd year comp sci students. I remember having to do a 'Towers Of Hanoi' solution, which consisted of endless hours staring at a blank screen untill by mind finally snapped, at which point I wrote about 10 or 15 lines of code which I never really understood afterwards once I regained my sanity. :v:


I can't remember what tail recursion was but I'll have a look into it. I ended up taking the easy way out and building up a nice simple list I could iterate through .

rsynnott

Oh, it's an acquired taste. Once you get used to it it can be quite enjoyable.