http://www.perlmonks.org?node_id=1003715


in reply to Re^2: Mark Jason Dominus And Me - The Partition Problem
in thread Mark Jason Dominus And Me - The Partition Problem

Just an additional point. When you'll go further down into MJD's brilliant Higher Order Perl, you'll find out that he warns about problems about recursion (paragraph 1.8, "Where Recursion Blows"), in which he revisits the Fibonacci and Partition problems for larger Fibonacci numbers or larger collections of treasures) and that, later in the book, he is spending quite a bit of time on methods to get rid of recursion (especially Chapter 5, "From Recursion To Iterators, but not only there).

Recursion is a beautiful model not only when you have a predefined tree structure (such as the directory walk example), but also when a problem is very complicated, you often need to reduce it to a collection of smaller or simpler problems, and possibly again and again, until the individual problems become (almost) trivial (this is what divide and conquer algorithms are about). As an example, some of the efficient sort algorithms just do that, although their actual implementation may well have no recursive call at all. You may also want to use recursion if you want to generate all subsets of a set, or combinations or permutations. This may seem to be maths, but it is quite commonly necessary in software engineering. Many of the Operational Research problems also often fall into the category of candidates for recursion.

In brief, recursion gives you a very powerful tool to modeling complex problems, especially when you want to make sure that you have examined absolutely all possibilities. The downside is that, sometimes, recursion will let you visit each possibility a number of times, possibly a huge number of times (there are some ways around that to a certain extent, one of them being caching, which MJD examines in some depth, but not always). So, sometimes you use recursion to better understand the problem and how to solve it, but then change it to iteration or something else when is comes to actual implementation. In such cases, recursion can be thought of as a prototype.

Reading further MJD's book, you will also find out that even for directory walk, recursion is not necessarily the best solution, the reason being that recursion is very good at depth-first traversing of the directory tree; but sometimes you need to traverse the tree in breadth-first order (or some other order), and then, recursion becomes very unpractical to use.

Keep reading this excellent book. I really did not have any problem with recursion when I first read it, but I learned an awful lot of other things from it, and there are other with which I am still fighting after having read them three times. There are some chapters that I will probably read for the fourth time, because I haven't fully understood their full implications and I still have quite a but to learn for them.

Replies are listed 'Best First'.
Re^4: Mark Jason Dominus And Me - The Partition Problem
by Dominus (Parson) on Nov 14, 2012 at 18:12 UTC

      OK, I missed a word, sorry about that. And English not being my mother tongue, I did not realize that it might sound as a profanity before reading your comment.

        I think it is safe to assume that MJD was not being ironic/sarcastic.

        And I know, as someone who has never managed to attain any degree of fluency in a 2nd language, that I am very, very lucky that my nursery language turned out to be the de facto international language of computers.

        I think MJD is saying "I understand it's an unintentional dropped word, but you have suddenly made this very funny when it was just a rather dull chapter title, and I really like this -- and I wish I had thought of it first."

        Explaining jokes: nothing funnier than an autopsy.

Re^4: Mark Jason Dominus And Me - The Partition Problem
by tilly (Archbishop) on Nov 14, 2012 at 02:43 UTC
    Indeed. People who only know how to traverse a directory using recursion will suffer grief if they are asked to do it breadth-first instead. Recursion gives you an implicit stack. If you can unwind it to get an explicit stack instead, then switching between depth-first and breadth-first is as simple as switching from a stack to a queue.

    But, one step at a time. Recursion is a great technique for thinking through a problem that you don't know how solve up front. Once you understand that solution, you can start trying to think of other approaches with other trade-offs. :-)