have you ever used recursion on the NES?

Just curious. I was thinking about this. Are there really any problems in NES programming that would be solved better through recursion than some other means? I got really into SNES SimCity for a while and I read a post on another blog/forum once (I forget where) about how power propagates out from power plants. something like that might be a good use for it, but I don't know how the NES version does it. It feels like the NES stack isn't really big enough to do anything with recursion that a loop couldn't do with less overhead. So how about it? Have you used recursion on the NES?

Recursion is rare because of how awkward it is to store values in the stack and how awkward it is to have nested data structures.

I've used it a few times though. Last time I did was for a byte-pair decompression subroutine, which is an inherently recursive algorithm.

Not very often.

I think I used one instance of recursion in Lizard, where you could stack blocks on top of each other. Moving the bottom block in a stack could shift blocks on top of it recursively. Source code here. Despite implementing this, though, I don't think I ever put more than two blocks in a room you could reach.

Visual demonstration. If you have the game (or its demo), you can enter the password 16472, then hold A + Select before pressing Up to enter the password door. That will take you to this test room.

I use recursion all the time (not on the NES), it's easy to make compact and reasonably efficient code that handles an unknown number of items. Non-tail recursive stuff is always going to be faster with an iterative version though, and knowing that the code won't have a stack overflow is nice to know. So far my NES games have always dealt with a known (and small) number of items, so I haven't even thought of making recursive versions of anything.

Not quite the same thing, but I do use tail recursion in my C code quite a bit for implementing things like game states.

Something like this:


The assembly generated by this is nice and predictable. I've used similar constructs in my coroutine code.

A* maybe...without looking at the code, I think I looped over a FIFO queue.

Building metatiles out of metatiles out of metatiles could be a candidate, but you usually have a fixed depth so not much to gain there.

To be honnest, no, there's no way I've ever used recursion on the NES. I've however have a subroutine call it's own end, but only once, not in a recursive fashion.

Basically it's jut an optimiation, when a "ACBC" pattern happens in code, instead of :

I'm not sure this is really a "NES thing" but moreso a general "have you ever used recursion on the 6502, and if so, to solve what thing?" question. But an excellent question BTW.

I remember using recursion in a couple ways in a IIGS demo I worked on, but I can't remember exactly for what. I just remember it being a lot easier to do/deal with than the alternate, in whatever circumstance it was.

I expect Garth on the forum might have some some good use-case examples of where recursion comes in handy.

Hey, all. Please stop bragging about your own projects! It would be much more appropriate to talk about Magic Floor, that is my project, and its "compute number of possible moves" function would be actually faster with recursive calls (for each newly entered map cell), that could work fine on a Z80 with about 1K free RAM, but on a NES it would require using a separate 16bit memory pointer (instead of the 8bit stack pointer), and an Atari 2600 wouldn't have enough RAM for that purpose at all. Instead of recursive calls, the game is flagging map cells as "needed to be processed later", the drawback is that the later processing requires to search through all map cells to find out which ones were flagged that way.
Other than that, in PC code, I am using recursive calls maybe once in 2-3 years, for things like crawling sub directories inside of sub directories, when creating a filesystem tree. Or in compression functions.

Implementing a flood fill for a drawing program I think of as the canonical case for recursion. For every point you need to branch out to its 4 neighbours. Kind of a perfect fit for the need.

It's also maybe a nice learning case study, because while it's extremely simple to implement as recursion, on a lot of platforms you'll probably crash the stack because of how many pixels are involved once your flood area is large enough. (Unfortunately might not give such a teaching experience on modern platforms with giant stacks.)

So... flood fill was also the thing that taught me how to build your own stack and do it without subroutine recursion. A good learning experience about how and why and when that's important to do as well.

My Game Boy port of Magic Floor likewise marks cells as ready for evaluation and makes multiple passes until evaluation settles, as does indoor/outdoor testing in RHDE. In both, it's subjectively "fast enough".

Ultimately, what makes "ready for evaluation"-based flood fill algorithms slow is that they behave like bubble sort: they propagate reachability slowly in the direction opposite that of scanning the array. For example, scanning from top to bottom makes propagation up take longer. Filling to the left or right is iterative (and thus fast). When it marks cells in the previous and next rows as ready for evaluation, the cells in the next row are quickly taken care of during the same scan. These cells in the next row are analogous to "rabbits" in bubble sort. But cells in the previous row have to wait for the next scan, like "turtles" in bubble sort.

Two extensions to bubble sort address the problem of turtles. The first is to make evaluation passes in opposite directions each time, producing cocktail sort. Applying bidirectional scanning to flood fill is also straightforward. Another is to compare cells several spaces apart, as in comb sort. This doesn't extend so easily to flood fill in the typical 4-direction or 8-direction connectedness definitions.

Cocktail sort wouldn't help Magic Floor though. In my tests, bidirectional scanning doesn't appreciably reduce the number of passes when determining reachability in this case. I implemented bidirectional reachability search in the Python prototype of floor generation. It didn't have noticeable effect on number of passes needed to solve reachability on smaller floors (2x8, 4x4, 6x4), where most floors are solved in 4 or 5 passes. For larger floors (6x6 or 8x6), the solution reduced from 5-7 passes to 4-6. I assume the improvement is so modest because the game defines connectedness to allow 2-cell moves, which reduces turtles anyway by allowing "ready for evaluation" state to propagate up two rows in one pass.

Puyo Puyo determines matches by a connected region of at least four cells of the same color. After a line clear and explosion, Bombliss breaks the remaining mass of blocks into connected regions and applies gravity to those regions that have not yet landed. Both are on Famicom and Game Boy. Rampart (Konami) for Famicom and Rampart (Jaleco) for NES use 8-way connectivity for indoor/outdoor testing. Has anyone debugged into those to see whether they use recursion?

the SNES's stack is no better then the NES

Most things that are small enough to be used recursively are also small enough to convert so they don't use recursion. I think I've used it a few times though, its kind of painful to use though.

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,

I get the feeling you're trying to make a statement about something, but it's just a little bit too subtle...

Some notes accompanying the leaked prototype and the efforts to make a commented disassembly claim it's done recursively:



It's also possible to do power-propagation style rules iteratively across simulation ticks with a cellular automaton.

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.

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.

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.

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:



(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).

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).

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

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

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.