Real-world examples of recursion [closed]

Question

What are real-world problems where a recursive approach is the natural solution besides depth-first search (DFS)?

(I don't consider Tower of Hanoi, Fibonacci number, or factorial real-world problems. They are a bit contrived in my mind.)

Answer 1

There are lots of mathy examples here, but you wanted a real world example, so with a bit of thinking, this is possibly the best I can offer:

You find a person who has contracted a given contageous infection, which is non fatal, and fixes itself quickly( Type A) , Except for one in 5 people ( We'll call these type B ) who become permanently infected with it and shows no symptoms and merely acts a spreader.

This creates quite annoying waves of havoc when ever type B infects a multitude of type A.

Your task is to track down all the type Bs and immunise them to stop the backbone of the disease. Unfortunately tho, you cant administer a nationwide cure to all, because the people who are typeAs are also deadly allergic to the cure that works for type B.

The way you would do this, would be social discovery, given an infected person(Type A), choose all their contacts in the last week, marking each contact on a heap. When you test a person is infected, add them to the "follow up" queue. When a person is a type B, add them to the "follow up" at the head ( because you want to stop this fast ).

After processing a given person, select the person from the front of the queue and apply immunization if needed. Get all their contacts previously unvisited, and then test to see if they're infected.

Repeat until the queue of infected people becomes 0, and then wait for another outbreak..

( Ok, this is a bit iterative, but its an iterative way of solving a recursive problem, in this case, breadth first traversal of a population base trying to discover likely paths to problems, and besides, iterative solutions are often faster and more effective, and I compulsively remove recursion everywhere so much its become instinctive. .... dammit! )

Answer 2

A real world example of recursion

Answer 3

How about anything involving a directory structure in the file system. Recursively finding files, deleting files, creating directories, etc.

Here is a Java implementation that recursively prints out the content of a directory and its sub-directories.

import java.io.File;

public class DirectoryContentAnalyserOne implements DirectoryContentAnalyser {

    private static StringBuilder indentation = new StringBuilder();

    public static void main (String args [] ){
        // Here you pass the path to the directory to be scanned
        getDirectoryContent("C:\\DirOne\\DirTwo\\AndSoOn");
    }

    private static void getDirectoryContent(String filePath) {

        File currentDirOrFile = new File(filePath);

        if ( !currentDirOrFile.exists() ){
            return;
        }
        else if ( currentDirOrFile.isFile() ){
            System.out.println(indentation + currentDirOrFile.getName());
            return;
        }
        else{
            System.out.println("\n" + indentation + "|_" +currentDirOrFile.getName());
            indentation.append("   ");

            for ( String currentFileOrDirName : currentDirOrFile.list()){
                getPrivateDirectoryContent(currentDirOrFile + "\\" + currentFileOrDirName);
            }

            if (indentation.length() - 3 > 3 ){
                indentation.delete(indentation.length() - 3, indentation.length());
            }
        }       
    }

}

Answer 4

Quicksort, merge sort, and most other N-log N sorts.

Answer 5

Matt Dillard's example is good. More generally, any walking of a tree can generally be handled by recursion very easily. For instance, compiling parse trees, walking over XML or HTML, etc.

Answer 6

Recursion is often used in implementations of the Backtracking algorithm. For a "real-world" application of this, how about a Sudoku solver?

Answer 7

Recursion is appropriate whenever a problem can be solved by dividing it into sub-problems, that can use the same algorithm for solving them. Algorithms on trees and sorted lists are a natural fit. Many problems in computational geometry (and 3D games) can be solved recursively using binary space partitioning (BSP) trees, fat subdivisions, or other ways of dividing the world into sub-parts.

Recursion is also appropriate when you are trying to guarantee the correctness of an algorithm. Given a function that takes immutable inputs and returns a result that is a combination of recursive and non-recursive calls on the inputs, it's usually easy to prove the function is correct (or not) using mathematical induction. It's often intractable to do this with an iterative function or with inputs that may mutate. This can be useful when dealing with financial calculations and other applications where correctness is very important.

Answer 8

Surely that many compilers out there use recursion heavily. Computer languages are inherently recursive themselves (i.e., you can embed 'if' statements inside other 'if' statements, etc.).

Answer 9

Disabling/setting read-only for all children controls in a container control. I needed to do this because some of the children controls were containers themselves.

public static void SetReadOnly(Control ctrl, bool readOnly)
{
    //set the control read only
    SetControlReadOnly(ctrl, readOnly);

    if (ctrl.Controls != null && ctrl.Controls.Count > 0)
    {
        //recursively loop through all child controls
        foreach (Control c in ctrl.Controls)
            SetReadOnly(c, readOnly);
    }
}

Answer 10

Famous Eval/Apply cycle from SICP

_{(source: mit.edu)}

Here is the definition of eval:

(define (eval exp env)
  (cond ((self-evaluating? exp) exp)
        ((variable? exp) (lookup-variable-value exp env))
        ((quoted? exp) (text-of-quotation exp))
        ((assignment? exp) (eval-assignment exp env))
        ((definition? exp) (eval-definition exp env))
        ((if? exp) (eval-if exp env))
        ((lambda? exp)
         (make-procedure (lambda-parameters exp)
                         (lambda-body exp)
                         env))
        ((begin? exp) 
         (eval-sequence (begin-actions exp) env))
        ((cond? exp) (eval (cond->if exp) env))
        ((application? exp)
         (apply (eval (operator exp) env)
                (list-of-values (operands exp) env)))
        (else
         (error "Unknown expression type - EVAL" exp))))

Here is the definition of apply:

(define (apply procedure arguments)
  (cond ((primitive-procedure? procedure)
         (apply-primitive-procedure procedure arguments))
        ((compound-procedure? procedure)
         (eval-sequence
           (procedure-body procedure)
           (extend-environment
             (procedure-parameters procedure)
             arguments
             (procedure-environment procedure))))
        (else
         (error
          "Unknown procedure type - APPLY" procedure))))

Here is the definition of eval-sequence:

(define (eval-sequence exps env)
  (cond ((last-exp? exps) (eval (first-exp exps) env))
        (else (eval (first-exp exps) env)
              (eval-sequence (rest-exps exps) env))))

eval -> apply -> eval-sequence -> eval

Answer 11

Recursion is used in things like BSP trees for collision detection in game development (and other similar areas).

Answer 12

People often sort stacks of documents using a recursive method. For example, imagine you are sorting 100 documents with names on them. First place documents into piles by the first letter, then sort each pile.

Looking up words in the dictionary is often performed by a binary-search-like technique, which is recursive.

In organizations, bosses often give commands to department heads, who in turn give commands to managers, and so on.

Answer 13

Parsers and compilers may be written in a recursive-descent method. Not the best way to do it, as tools like lex/yacc generate faster and more efficient parsers, but conceptually simple and easy to implement, so they remain common.

Answer 14

Real world requirement I got recently:

Requirement A: Implement this feature after thoroughly understanding Requirement A.

Answer 15

Recursion is applied to problems (situations) where you can break it up (reduce it) into smaller parts, and each part(s) looks similar to the original problem.

Good examples of where things that contain smaller parts similar to itself are:

• tree structure (a branch is like a tree)
• lists (part of a list is still a list)
• containers (Russian dolls)
• sequences (part of a sequence looks like the next)
• groups of objects (a subgroup is a still a group of objects)

Recursion is a technique to keep breaking the problem down into smaller and smaller pieces, until one of those pieces become small enough to be a piece-of-cake. Of course, after you break them up, you then have to "stitch" the results back together in the right order to form a total solution of your original problem.

Some recursive sorting algorithms, tree-walking algorithms, map/reduce algorithms, divide-and-conquer are all examples of this technique.

In computer programming, most stack-based call-return type languages already have the capabilities built in for recursion: i.e.

• break the problem down into smaller pieces ==> call itself on a smaller subset of the original data),
• keep track on how the pieces are divided ==> call stack,
• stitch the results back ==> stack-based return

Answer 16

I have a system that uses pure tail recursion in a few places to simulate a state machine.

Answer 17

Some great examples of recursion are found in functional programming languages. In functional programming languages (Erlang, Haskell, ML/OCaml/F#, etc.), it's very common to have any list processing use recursion.

When dealing with lists in typical imperative OOP-style languages, it's very common to see lists implemented as linked lists ([item1 -> item2 -> item3 -> item4]). However, in some functional programming languages, you find that lists themselves are implemented recursively, where the "head" of the list points to the first item in the list, and the "tail" points to a list containing the rest of the items ([item1 -> [item2 -> [item3 -> [item4 -> []]]]]). It's pretty creative in my opinion.

This handling of lists, when combined with pattern matching, is VERY powerful. Let's say I want to sum a list of numbers:

let rec Sum numbers =
    match numbers with
    | [] -> 0
    | head::tail -> head + Sum tail

This essentially says "if we were called with an empty list, return 0" (allowing us to break the recursion), else return the value of head + the value of Sum called with the remaining items (hence, our recursion).

For example, I might have a list of URLs, I think break apart all the URLs each URL links to, and then I reduce the total number of links to/from all URLs to generate "values" for a page (an approach that Google takes with PageRank and that you can find defined in the original MapReduce paper). You can do this to generate word counts in a document also. And many, many, many other things as well.

You can extend this functional pattern to any type of MapReduce code where you can taking a list of something, transforming it, and returning something else (whether another list, or some zip command on the list).

Answer 18

XML, or traversing anything that is a tree. Although, to be honest, I pretty much never use recursion in my job.

Answer 19

Feedback loops in a hierarchical organization.

Top boss tells top executives to collect feedback from everyone in the company.

Each executive gathers his/her direct reports and tells them to gather feedback from their direct reports.

And on down the line.

People with no direct reports -- the leaf nodes in the tree -- give their feedback.

The feedback travels back up the tree with each manager adding his/her own feedback.

Eventually all the feedback makes it back up to the top boss.

This is the natural solution because the recursive method allows filtering at each level -- the collating of duplicates and the removal of offensive feedback. The top boss could send a global email and have each employee report feedback directly back to him/her, but there are the "you can't handle the truth" and the "you're fired" problems, so recursion works best here.

Answer 20

Suppose you are building a CMS for a website, where your pages are in a tree structure, with say the root being the home-page.

Suppose also your {user|client|customer|boss} requests that you place a breadcrumb trail on every page to show where you are in the tree.

For any given page n, you'll may want to walk up to the parent of n, and its parent, and so on, recursively to build a list of nodes back up to the root of page tree.

Of course, you're hitting the db several times per page in that example, so you may want to use some SQL aliasing where you look up page-table as a, and page-table again as b, and join a.id with b.parent so you make the database do the recursive joins. It's been a while, so my syntax is probably not helpful.

Then again, you may just want to only calculate this once and store it with the page record, only updating it if you move the page. That'd probably be more efficient.

Anyway, that's my $.02

Answer 21

You have an organization tree that is N levels deep. Several of the nodes are checked, and you want to expand out to only those nodes that have been checked.

This is something that I actually coded. Its nice and easy with recursion.

Answer 22

In my job we have a system with a generic data structure that can be described as a tree. That means that recursion is a very effective technique to work with the data.

Solving it without recursion would require a lot of unnecessary code. The problem with recursion is that it is not easy to follow what happens. You really have to concentrate when following the flow of execution. But when it works the code is elegant and effective.

Answer 23

Calculations for finance/physics, such as compound averages.

Answer 24

• Parsing an XML file.
• Efficient search in multi-dimensional spaces. E. g. quad-trees in 2D, oct-trees in 3D, kd-trees, etc.
• Hierarchical clustering.
• Come to think of it, traversing any hierarchical structure naturally lends itself to recursion.
• Template metaprogramming in C++, where there are no loops and recursion is the only way.

Answer 25

Parsing a tree of controls in Windows Forms or WebForms (.NET Windows Forms / ASP.NET).

Answer 26

The best example I know is quicksort, it is a lot simpler with recursion. Take a look at:

shop.oreilly.com/product/9780596510046.do

www.amazon.com/Beautiful-Code-Leading-Programmers-Practice/dp/0596510047

(Click on the first subtitle under the chapter 3: "The most beautiful code I ever wrote").

Answer 27

Phone and cable companies maintain a model of their wiring topology, which in effect is a large network or graph. Recursion is one way to traverse this model when you want to find all parent or all child elements.

Since recursion is expensive from a processing and memory perspective, this step is commonly only performed when the topology is changed and the result is stored in a modified pre-ordered list format.

Answer 28

Inductive reasoning, the process of concept-formation, is recursive in nature. Your brain does it all the time, in the real world.

Answer 29

Ditto the comment about compilers. The abstract syntax tree nodes naturally lend themselves to recursion. All recursive data structures (linked lists, trees, graphs, etc.) are also more easily handled with recursion. I do think that most of us don't get to use recursion a lot once we are out of school because of the types of real-world problems, but it's good to be aware of it as an option.

Answer 30

Multiplication of natural numbers is a real-world example of recursion:

To multiply x by y
  if x is 0
    the answer is 0
  if x is 1
    the answer is y
  otherwise
    multiply x - 1 by y, and add x