Dictionary definition of recursion: See Recursion.
Alright that joke’s an oldie but it’s also a goodie because it completely sums up the essence of recursion, which (in programming terms) is simply the use of a function which is able to call itself.
Most commonly recursion is an ideal solution for problems that can be attacked with a divide and conquer approach. That is, where one task needs to be repeated multiple times on a given input.
Such a task might be an HTML parser. HTML allows complex nesting structures such as multiply nested formatting tags like and , along with their accompanying closing tags and . To properly interpret HTML it is necessary to follow such nesting all the way into the innermost nest and back out again. Along the way there may be many other objects nested such as
and so on.
An HTML parser will approach this by dividing and conquering. A recursive function will examine the HTML and as soon as it encounters the first or other tag it will then call itself to search for more tags. Each time a new one is encountered it will call itself again. And each time a closing tag is found it will return from the function back to the previous iteration until the final closing is found. Along the way the parser will build a data structure from what it discovers.
Writing such a parser is quite a large project and there is a lot to take into account, such as badly matched nesting or even missing closing tags and so on, so we won’t go into that in this article. Instead we’ll take a look at a couple of smaller problems as we examine just what recursion can do for us.
THIS IS A PREVIEW. DOWNLOAD ISSUE 12 TO READ THE FULL ARTICLE.