我应该避免使用在iPhone上运行的代码进行递归吗?
换句话说,有人知道iPhone上的最大堆栈大小吗?
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?
最满意答案
是的,避免递归对所有嵌入式平台都是好事。
它不仅可以降低甚至消除堆栈溢出的可能性,还可以为您提供更快的代码。
您始终可以重写递归算法以进行迭代。 虽然这并不总是实用的(想想快速排序)。 解决这个问题的方法是以递归深度有限的方式重写算法。
introsort是一个完美的例子,它是如何在实践中完成的。 它将快速排序的递归深度限制为log2(元素数)。 所以在32位机器上你永远不会超过32。
http://en.wikipedia.org/wiki/Introsort
我过去为嵌入式平台编写了相当多的软件(汽车娱乐系统,手机,游戏机等),我总是确保在递归深度上设置上限或者在第一次时避免递归地点。
因此,我的程序都没有因堆栈溢出而死亡,大多数程序都满意32kb的堆栈。 一旦你需要多个线程,每个线程获得自己的堆栈,这就可以节省大量时间。你可以通过这种方式节省数兆字节的内存。
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.
更多推荐
发布评论