have you ever used recursion on the NES?

[pubby]

Ibuild your own stack and do it without subroutine recursion

Or on the NES, use the hardware stack! It's good for this type of thing.

[rainwarrior]

build your own stack and do it without subroutine recursion

Or on the NES, use the hardware stack! It's good for this type of thing.

I don't think it'd actually be good for the flood fill problem because of the limited size, but to spell this out:

Yes, if you need a stack structure, it can be convenient to make a "temporary" stack on some unused portion of the stack page by manually moving it TSX/TXS, as long as you can put it back before making any JSR/RTS. Lets you use PHA/PLA to directly manipulate this temporary stack in a very succinct way.

[Garth]

I have hardly used it. Section 15 of my 6502 stacks treatise is about recursion though, at http://wilsonminesco.com/stacks/recurse.html . It naturally follows section 14 which is about local variables and environments.

What is funny about recursion is that the examples to show how amazing this is are always awful. Usually the fibonacci series is used as an example but theres a zillion reasons this is awful :

• Fibonnaci series has no practical uses, especially not in game development.
• Fibonnaci series would be better implemented as a lookup table, at least up to ~50 numbers.
• Even if you want to actually compute the Fibonacci series, recursion is less intuitive than loop
• And if you manage to do it with recursion, it's actually exponentially slower as more numbers goes up, and will soon bloat your stack and processing power, as each additional number doubles the amount of calculations. This is not the case with a loop.

So this idea of using recursion to compute fibonacci series is a very good example what NOT to do.

Factorial is less an awful idea because the time spent is still linear. But still it's less intuitive than loop, and is better done with a lookup table. It's only application is in probabilities calculations which often aren't done on computers, especially not video games,

Those points are brought up on the web page (except the part about game development). One of the hardest parts about writing the 6502 stacks treatise however was coming up with concise program examples that showed the principle without requiring an understanding of the background of an application. Most of my uses from my own work would involve technical things on the workbench; so those were out.

[slembcke]

Eh, I could point out plenty of examples of recursion in my non-NES projects for graph or tree algorithms. Realistically all of them are not feasible on the NES or 8 bit micros in general because they are for handling fairly large datasets. The code could be considerably more compact by using simpler algorithms like repeated linear searches. For the size of a dataset you could fit in < 64kb, the performance difference is not going to be as bad, especially if you can amortize it over several frames.

IMO, recursion is nice because it can make code simpler (both source and machine code size) at what is usually a mild performance reduction. If you can make something tail recursive then there is usually no performance difference. Part of the reason I love Compiler Explorer so much is that I can easily check that my compiler is doing what I think it is and focus on using patterns that are both simple and efficient.

[adam_smasher]

In higher-level languages, heavily recursive code can often look very declarative - a specification of what the output should be, seemingly without explicitly specifying how to compute it. An example might be this sorting algorithm in Haskell:

Code: Select all

qsort []	= []
qsort (x:xs) = qsort small ++ [x] ++ qsort large
  where
    small = [y | y<-xs, y<x]
    large = [y | y<-xs, y>x]

(to sort a list, take everything smaller than the first element, sort it; take everything larger than the first element, sort it; then stick the three together, in order)

Once you get the hang of this style, it can be extremely readable and very beautiful. But you're not really going to get a good sense of that in 6502 assembly language (or any assembly language, really).

[rainwarrior]

The Haskell "elegant quicksort" example is sort of in the same category as using recursion for a Fibonacci sequence. ;P Sure it's a succinct expression of the idea but it's very much not a good implementation of it.

...plus Haskell has a built in sort that is what you should actually use. Of course if you're trying to demonstrate the "power" of functional programming, calling a library sort function doesn't look very dramatic, and also doesn't distinguish it from any other language with a built in library.


That said, Haskell is probably a good language to do some exercises in if you want to learn about recursion. Since it makes recursion its standard way to iterate, you will quickly have to sink or swim by it.

It bears in mind, though, that Haskell is a very restricted language because of its functional programming paradigm. It's very rigorous about the boundaries of what a function can do, and that makes it possible for its JIT compiler to do a lot of effective things with recursion that most other languages can't. Lazy evaluation, tail calls, and even memoization are all built in features of Haskell's compiler implementation that are doing a lot of work to support this under the hood. The memoization in particular is effective in cases like that Fibonacci sequence, where having cached results will cut that O(N^2) recursion back down to O(N)... or maybe O(N log N).

[slembcke]

While a more efficient in-place version of QuickSort is more code, there is going to be a chunk of it that looks fundamentally similar to that Haskell version. Rewriting it to be purely iterative would be... hard. I mean you'd basically be emulating what a call stack just gives you as syntax in your language.

I have an in-place version of QuickHull (very similar algorithm for convex hulls) in Chipmunk2D, and even that has the "stuff before, pivot, stuff after" sequence in it.
https://github.com/slembcke/Chipmunk2D/ ... unk.c#L230

[rainwarrior]

Oh, sorry maybe I was drawing that off topic. Yes, quicksort is fundamentally a recursive algorithm.

I just mean that example is one you often see in article about "why Haskell is so great", and it's a really bad implementation of quicksort, partly because you're generating new lists at each stage, partly because you're causing twice as many comparisons by filtering the list twice, and partly 'cause it's a really bad pivot choice. Bizarrely, I think the moment you ask "but what if I want to use the middle element as a pivot?" it suddenly it becomes very clear how strongly the language works against solving that problem. This example is only half of what makes quicksort quicksort. ...but Haskell isn't actually bad at sorting, it has a perfectly good built in library sort.

The recursion part of the idea is totally fine though.

I'm not anti-Haskell at all either, there's definitely a place and time where it's a very useful language, just I always hated that Haskell quicksort. I do think some beginner tutorials on Haskell might help a lot with understanding recursion, though, as it's a language that maximally encourages it. (...but then again maybe it teaches you about some uses for recursion that don't apply elsewhere.)

http://learnyouahaskell.com/recursion

[slembcke]

Oh, sorry maybe I was drawing that off topic.

Well, not really. I guess my earlier point was that I often like recursive code for being concise and compact even though I know it's not always the most performant. Sometimes I even write it in interpreted languages. While I do quite enjoy code golf for the NES too, recursion just doesn't seem to be all that useful with small fixed size buffers.