Real-world examples of recursion

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

User · Answer

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.

User · Answer

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

User · Answer

If you have two different but similar sequences and want to match the components of each sequence such that large contiguous chunks are favored first followed by identical sequence order  then you can recursively analyze those sequences to form a tree and then recursively process that tree to flatten it   Reference  Recursion  amp  Memoization Example Code

User · Answer

Finding the median in average-case O n    Equivalent to finding the k-th largest item in a list of n things  with k n 2    int kthLargest list  k  first  last      j   partition list  first  last    if  k    j       return list j    else if  k   Here  partition picks a pivot element  and in one pass through the data  rearranges the list so that items less than the pivot come first  then the pivot  then items bigger than the pivot   The  kthLargest  algorithm is very similar to quicksort  but recurses on only one side of the list   For me  this is the simplest recursive algorithm that runs faster than an iterative algorithm   It uses 2 n comparisons on average  regardless of k   This is much better than the naive approach of running k passes through the data  finding the minimum each time  and discarding it   Alejo

User · Answer

The College Savings Plan  Let A n    amount saved for college after n months A 0     500 Each month    50 is deposited into an account which earns 5  in annual interest    Then A n    A n-1    50   0 05  1 12   A N-1

User · Answer

A method to generate a tree structured menu from a database table using subsonic   public MenuElement BHSSiteMap node  string role                if  CheckRole node  role                         ParentNode   node                  get site map collection order by sequence             BHSSiteMapCollection children   new BHSSiteMapCollection                 Query q   BHSSiteMap CreateQuery                        WHERE BHSSiteMap Columns Parent  Comparison Equals  ParentNode Id                       ORDER BY BHSSiteMap Columns Sequence   ASC                 children LoadAndCloseReader q ExecuteReader                  if  children Count  gt  0                                ChildNodes   new List lt MenuElement gt                      foreach  BHSSiteMap child in children                                        MenuElement childME   new MenuElement child  role                       ChildNodes Add childME

User · Answer

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

User · Answer

Recursion is a very basic programming technique  and it lends itself to so many problems that listing them is like listing all problems that can be solved by using addition of some kind   Just going through my Lisp solutions for Project Euler  I find  a cross total function  a digit matching function  several functions for searching a space  a minimal text parser  a function splitting a number into the list of its decimal digits  a function constructing a graph  and a function traversing an input file   The problem is that many if not most mainstream programming languages today do not have tail call optimization so that deep recursion is not feasible with them   This inadequacy means that most programmers are forced to unlearn this natural way of thinking and instead rely on other  arguably less elegant looping constructs

User · Answer

Quicksort  merge sort  and most other N-log N sorts

User · Answer

Plug  http   picogen deviantart com gallery

User · Answer

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

User · Answer

You have a building  The building has 20 rooms  Legally  you can only have a certain amount of people in each room  Your job is to automatically assign people to a room  Should I room get full  you need to find an available room  Given that only certain rooms can hold certain people  you also need to be careful on which room   For example   Rooms 1  2  3 can roll in to each other  This room is for kids who can t walk on their own  so you want them away from everything else to avoid distraction and other sickness  which isn t a thing to older people  but to a 6mo it can become very bad  Should all three be full  the person must be denied entrance   Rooms 4  5  6 can roll in to each other  This room is for people that are allergic to peanuts and thusly  they can not go in to other rooms  which may have stuff with peanuts   Should all three become full  offer up a warning asking their allergy level and perahsp they can be granted access   At any given time  rooms can change  So you may allow room 7-14 be no-peanut rooms  You don t know how many rooms to check   Or  perhaps you want to seperate based on age  Grade  gender  etc  These are just a couple examples I ve come in to

User · Answer

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

User · Answer

A  real-world  problem solved by recursion would be nesting dolls  Your function is OpenDoll     Given a stack of them  you would recursilvey open the dolls  calling OpenDoll   if you will  until you ve reached the inner-most doll

User · Answer

The last real world example I have is a pretty frivolous  but it demonstrates how recursion  just fits  sometimes   I was using the Chain of Responsibility pattern so a Handler object either handles a request itself  or delegates it down the chain  It s useful to log the construction of the chain   public String getChainString         cs   this getClass   toString        if this delegate    null            cs     - gt     delegate getChainString              return cs      You could argue that this isn t the purest recursion  because although the method calls  itself   it is in a different instance each time it s called

User · Answer

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

User · Answer

A real world example of recursion

User · Answer

A real world example of indirect recursion would be asking your parents if you can have that video game for christmas  Dad   Ask mom      Mom   Ask Dad    In short   No  but we dont want to tell you that lest you throw a tantrum

User · Answer

I think that this really depends upon the language  In some languages  Lisp for example  recursion is often the natural response to a problem  and often with languages where this is the case  the compiler is optimized to deal with recursion    The common pattern in Lisp of performing an operation on the first element of a list and then calling the function on the rest of the list in order to either accumulate a value or a new list is quite elegant and most natural way to do a lot of things in that language  In Java  not so much

User · Answer

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

User · Answer

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

User · Answer

Since you don t seem to like computer science or mathy examples  here is a different one  wire puzzles   Many wire puzzles involve removing a long closed loop of wire by working it in and out of wire rings   These puzzles are recursive   One of them is called  arrow dynamics    I am sue you could find it if you google for  arrow dynamics wire puzzle   These puzzles are a lot like the towers of Hanoi

User · Answer

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

User · Answer

I just wrote a recursive function to figure out if a class needed to be serialized using a DataContractSerializer   The big issue came with templates generics where a class could contain other types that needed to be datacontract serialized    so it s go through each type  if it s not datacontractserializable check it s types

User · Answer

Everything where you use iteration is done more natural with recursion if it where not for the practical limitation of causing a stack overflow  -   But seriously Recursion and Iteration are very interchangeable you can rewrite all algorithm using recursion to use iteration and vise versa   Mathematicians like recursion and programmers like iteration  That is probably also why you see all these contrived examples you mention  I think the method of mathematical proof called Mathematical induction has something to do why mathematicians like recursion  http   en wikipedia org wiki Mathematical induction

User · Answer

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

User · Answer

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

User · Answer

Methods for finding prime numbers are recursive  Useful for generating hash keys  for various encryption schemes that use factors of large numbers

User · Answer

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

User · Answer

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

User · Answer

Recursion is a very basic programming technique  and it lends itself to so many problems that listing them is like listing all problems that can be solved by using addition of some kind   Just going through my Lisp solutions for Project Euler  I find  a cross total function  a digit matching function  several functions for searching a space  a minimal text parser  a function splitting a number into the list of its decimal digits  a function constructing a graph  and a function traversing an input file   The problem is that many if not most mainstream programming languages today do not have tail call optimization so that deep recursion is not feasible with them   This inadequacy means that most programmers are forced to unlearn this natural way of thinking and instead rely on other  arguably less elegant looping constructs

User · Answer

I wrote a tree in C  to handle lookups on a table that a 6-segmented key with default cases  if key 0  doesn t exist  use the default case and continue    The lookups were done recursively   I tried a dictionary of dictionaries of dictionaries  etc  and it got way too complex very quickly   I also wrote a formula evaluator in C  that evaluated equations stored in a tree to get the evaluation order correct   Granted this is likely a case of choosing the incorrect language for the problem but it was an interesting exercise   I didn t see many examples of what people had done but rather libraries they had used   Hopefully this gives you something to think about

User · Answer

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

User · Answer

Finding the median in average-case O n    Equivalent to finding the k-th largest item in a list of n things  with k n 2    int kthLargest list  k  first  last      j   partition list  first  last    if  k    j       return list j    else if  k   Here  partition picks a pivot element  and in one pass through the data  rearranges the list so that items less than the pivot come first  then the pivot  then items bigger than the pivot   The  kthLargest  algorithm is very similar to quicksort  but recurses on only one side of the list   For me  this is the simplest recursive algorithm that runs faster than an iterative algorithm   It uses 2 n comparisons on average  regardless of k   This is much better than the naive approach of running k passes through the data  finding the minimum each time  and discarding it   Alejo

User · Answer

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  gt  3                    indentation delete indentation length   - 3  indentation length

User · Answer

Calculations for finance physics  such as compound averages

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

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

User · Answer

We use them to do SQL path-finding   I will also say it s painstaking to debug  and it s very easy for a poor programmer to screw it up

User · Answer

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

User · Answer

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

User · Answer

Everything where you use iteration is done more natural with recursion if it where not for the practical limitation of causing a stack overflow  -   But seriously Recursion and Iteration are very interchangeable you can rewrite all algorithm using recursion to use iteration and vise versa   Mathematicians like recursion and programmers like iteration  That is probably also why you see all these contrived examples you mention  I think the method of mathematical proof called Mathematical induction has something to do why mathematicians like recursion  http   en wikipedia org wiki Mathematical induction

User · Answer

Methods for finding a square root are recursive  Useful for calculating distances in the real world

User · Answer

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

User · Answer

I wrote an XML parser once that would have been much harder to write without recursion   I suppose you can always use a stack   iteration  but sometimes recursion is just so elegant

User · Answer

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          - gt  0       head  tail - gt  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

User · Answer

Geometric calculations for GIS or cartography  such as finding the edge of a circle

User · Answer

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- gt 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

User · Answer

Towers of Hanoi  Here s one you can interact with  http   www mazeworks com hanoi      Using recurrence relations  the exact number of moves that this solution requires can be calculated by  2h - 1  This result is obtained by noting that steps 1 and 3 take Th - 1 moves  and step 2 takes one move  giving Th   2Th - 1   1    See  http   en wikipedia org wiki Towers of hanoi Recursive solution

User · Answer

Anything program with tree or graph data structures will likely have some recursion

User · Answer

Parsing a tree of controls in Windows Forms or WebForms   NET Windows Forms   ASP NET

User · Answer

Check if the created image is going to work within a size restricted box    function check size  font size   font   text   width   height            if   is string  text                 throw new Exception  Invalid type for  text                          box   imagettfbbox  font size  0   font   text            box  width     abs  box 2  -  box 0            if   box 0   lt  -1                 box  width     abs  box 2     abs  box 0   - 1                        box  height     abs  box 7   - abs  box 1            if   box 3   gt  0                 box  height     abs  box 7  - abs  box 1    - 1                       return   box  height    lt   height  amp  amp   box  width    lt   width    array  font size   box  width     height     this- gt check size  font size - 1   font   text   width   height

User · Answer

Write a function that translates a number like 12345 67 to  twelve thousand three hundred forty-five dollars and sixty-seven cents

User · Answer

Real world requirement I got recently   Requirement A  Implement this feature after thoroughly understanding Requirement A

User · Answer

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  amp  amp  ctrl Controls Count  gt  0                  recursively loop through all child controls         foreach  Control c in ctrl Controls              SetReadOnly c  readOnly

User · Answer

Mostly recursion is very natural for dealing with recursive data structures  This basically means list structures  and tree structures  But recursion is also a nice natural way of  creating  tree structures on the fly in some way  by divide-and-conquer for instance quicksort  or binary search   I think your question is a bit misguided in one sense  What s not real-world about depth first search  There s a lot you can do with depth-first search   For instance  another example I thought of giving is recursive descent compilation  It is enough of a real-world problem to have been used in many real-world compilers  But you could argue it is DFS  it is basically a depth-first-search for a valid parse tree

[recursion] Real-world examples of recursion

Examples related to recursion