This week, I am supposed to talk about recursion. Since I have already did an entry on the basics of that particular technique of coding, this week I shall discuss about a question that is frequently asked in computer science - Are there algorithms that can only be solved recursively?
Well, it turns out that the answer is yes and no.
No, theoretically, an advanced programmer may be able to make use of a Last-in-first-out (LIFO) stack that keeps a running list of the remaining tasks to handle the whole recursive process in a while loop which continues to push and pop tasks until the list is empty. This method is the most common among all the other workarounds, and is recognized by making the observation that recursion in programming is really just a special case of iteration.
On the other hand, in mathematical terms, yes, there are indeed certain problems that require recursion to arrive at an answer. A simple example is the Newton-Raphson method (learned in mat137). Another famous example is the Ackermann function. Of course, as mentioned earlier, in coding, one can always manage a stack to emulate the recursive calls on the function itself.
No comments:
Post a Comment