Recursion works best when the algorithm uses a data structure that naturally supports recursion. For example, Trees are a naturally recursive structure and recursion works well with them. In other cases, the algorithm is naturally suited to recursion. For example, the binary search algorithm lends itself to a natural recursive algorithm. On the other hand, not all looping algorithms can or should be implemented with a recursion.
Recursive solutions may involve extensive overhead because they use calls. When a call is made, it takes time to build a stackframe and push it into the stack. Conversely, when a return is executed, the stackframe must be popped from the stack and the local variables reset to their previous values. Again, this takes time. A recursive algorithm therefore generally runs slower than its nonrecursive implementation.
Each time we make a call we use up some of our memory allocation. If the recursion is deep – that is, if there are many recursive calls – then we may run out of memory. Therefore, the algorithms we have discussed so far (factorial and powers) are better developed iteratively if large numbers are involved. As a general rule, recursive algorithms should be used only when their efficiency is logarithmic.
No comments:
Post a Comment