Should I avoid recursion on the iPhone?

Question

Should I avoid recursion with code that runs on the iPhone?

Or put another way, does anyone know the max stack size on the iphone?

Answer 1

Yes, avoiding recursion is a good thing on all embedded platforms.

Not only does it lowers or even removes the chance of a stack-overflow, it often gives you faster code as well.

You can always rewrite a recursive algorithm to be iterative. That's not always practical though (think quicksort). A way to get around this is to rewrite the algorithms in a way that the recursion depth is limited.

The introsort is a perfect example how it's done in practice. It limits the recursion depth of a quicksort to log2 (number-of-elements). So on a 32 bit machine you will never recurse deeper than 32.

http://en.wikipedia.org/wiki/Introsort

I've written quite a bit of software for embedded platforms in the past (car entertainment systems, phones, game-consoles and the like) and I always made sure that I put a upper limit on the recursion depth or avoided recursion at the first place.

As a result none of my programs ever died with a stack-overflow and most programs are happy with 32kb of stack. This pays off big time once you need multiple threads as each thread gets it's own stack.. You can save megabytes of memory that way.

Answer 2

The max stack size on the iphone?

The iPhone runs a modified OSX in which every process is given a valid memory space, just like in most operating systems.

It's a full processor, so stack grows up, and heap grows down (or vice versa depending on your perspective). This means that you won't overflow the stack until you run out of memory allocated to your program.

It's best to avoid recursion when you can for stack and performance reasons (function calls are expensive, relative to simple loops), but in any case you should decide what limits you can place on recursive functions, and truncate them if they go too long.

Answer 3

I see a couple of answers that boil down to "don't use recursion". I disagree - it's not like the iPhone is some severely-constrained embedded system. If a problem is inherently recursive, feel free to express it that way.

Unless you're recursing to a stack depth of hundreds or thousands of frames, you'll never have an issue.