Tweet
You're asking for an example of a recursive function in a game? I don't think I can really do that for you. Recursion is one of those things that's a godsend when you need it, but 99.9% of the time you don't. If you're going to find recursion in a game, it would be something of a unicorn hunt in the high-level code. My guess is that you'd be more likely to find it in lower-level routines for rendering and media playback, but if there's a consistent need for recursion even at that level, it's likely to be encapsulated in drivers or on the hardware.
The main reason is that true recursion requires the function to call itself, and the recursive calls continue to whatever depth is required. Then the whole thing bubbles back up to the original call. This is time-consuming and can be relatively costly in terms of system resources, which isn't good for a game. They have some large number of things they have to do in each game tick/frame, and waiting a recursive chain to complete can easily eat up too many cycles. Games typically function as "state machines", and break tasks down into units of what's required each frame. So if there actually was a task that might ordinarily lend itself well to recursion, it would probably be broken up into enough states to cover the worst case scenario of the game, and some part of it would be handled in each tick.
A decay function for a sound effect might be a good example of something a game could conceivably handle recursively, but you'd have to look at the audio hardware. Even in the PS 1 days, that was something you requested from the SPU. If the SPU in some way does it recursively through software, it doesn't affect the game engine so much because a purpose-built piece of hardware is handling it. I'm about 90% sure that's all handled on the metal, though.
In general computing terms, the go-to example of recursion is computing a factorial, e.g., 5! = 5 * 4 * 3 * 2 * 1. You can find examples of that all over the place. For something that might actually show up in gaming, you'd probably want to look to anything that has to handle syntax according to some sort of defined grammar. That is, anything that looks like a compiler or an interpreter. Any development kit for a game engine is likely to include some amount of recursion for handling syntax trees created in whatever scripting language they use. Hell, Omniconvert (a tool for converting PS2 codes between different cheat devices) has a small amount of recursion in it to handle nested conditional codes. Most PS2 cheat devices embed counts in the conditional codes, but the AR MAX uses terminator lines instead, so conditional code types go through a recursive algorithm that keeps track of how many lines are in the original and converted codes, and what the counts should be or where the terminators should be inserted. It also helps with validity checking. That tool is open source, if you want to take a look at it.
The main reason is that true recursion requires the function to call itself, and the recursive calls continue to whatever depth is required. Then the whole thing bubbles back up to the original call. This is time-consuming and can be relatively costly in terms of system resources, which isn't good for a game. They have some large number of things they have to do in each game tick/frame, and waiting a recursive chain to complete can easily eat up too many cycles. Games typically function as "state machines", and break tasks down into units of what's required each frame. So if there actually was a task that might ordinarily lend itself well to recursion, it would probably be broken up into enough states to cover the worst case scenario of the game, and some part of it would be handled in each tick.
A decay function for a sound effect might be a good example of something a game could conceivably handle recursively, but you'd have to look at the audio hardware. Even in the PS 1 days, that was something you requested from the SPU. If the SPU in some way does it recursively through software, it doesn't affect the game engine so much because a purpose-built piece of hardware is handling it. I'm about 90% sure that's all handled on the metal, though.
In general computing terms, the go-to example of recursion is computing a factorial, e.g., 5! = 5 * 4 * 3 * 2 * 1. You can find examples of that all over the place. For something that might actually show up in gaming, you'd probably want to look to anything that has to handle syntax according to some sort of defined grammar. That is, anything that looks like a compiler or an interpreter. Any development kit for a game engine is likely to include some amount of recursion for handling syntax trees created in whatever scripting language they use. Hell, Omniconvert (a tool for converting PS2 codes between different cheat devices) has a small amount of recursion in it to handle nested conditional codes. Most PS2 cheat devices embed counts in the conditional codes, but the AR MAX uses terminator lines instead, so conditional code types go through a recursive algorithm that keeps track of how many lines are in the original and converted codes, and what the counts should be or where the terminators should be inserted. It also helps with validity checking. That tool is open source, if you want to take a look at it.
Comment