Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl: the Markov chain saw

Comment on

( #3333=superdoc: print w/replies, xml ) Need Help??

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.

In reply to Re^3: Mark Jason Dominus And Me - The Partition Problem by Laurent_R
in thread Mark Jason Dominus And Me - The Partition Problem by Tommy

Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":

  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.
  • Log In?

    What's my password?
    Create A New User
    and all is quiet...

    How do I use this? | Other CB clients
    Other Users?
    Others about the Monastery: (3)
    As of 2017-06-29 06:30 GMT
    Find Nodes?
      Voting Booth?
      How many monitors do you use while coding?

      Results (653 votes). Check out past polls.