Real-world examples of recursion [closed]

Want to improve this question? Update the question so it focuses on one problem only by editing this post.

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.)

Thanks for all the suggestions but everyone is suggest tree/network traversals. Theses are essentially all examples of Depth-First-Search (or BFS I guess). I was looking for other well motivated algorithms/problems.

I like this question! "Tell me all the uses of technique X, EXCEPT the main practical use of technique X"

I use recursion all the time but usually for mathy and graphy things. I'm trying to look for examples of recursion that would be meaningful to non-programmers.

Choose your own adventure novels! I want to read the whole thing, and recursion is the best way to do so.

There is no recursion in the real-world. Recursion is a mathematical abstraction. You can model lots of things using recursion. In that sense, Fibonacci is absolutely real-world, as there are quite some real-world problems that can be modeled this way. If you think that Fibonacci is not real-world, than I would claim that all other examples are abstractions as well, not real-world examples.

55 Answers 55

A real world example of recursion

How's this recursive? Sure, it's pretty. But recursive? A fractal cabbage would have worked nicely, but I don't see self-similarities in this flower.

Well it's a bit tounge in cheek, but it's an example of phyllotaxis, which can be described with the Fibonacci sequence, which is commonly implemented through recursion.

"commonly implemented through recursion" doesn't necessarily mean that the flower does so. Perhaps it does; I'm not enough of a molecular biologist to know, but without an explanation about how it does, I don't see this as particularly helpful. Downvoting. If you want to add a description (whether or not it's biologically accurate, it might lend insight) to accompany it, I'll happily reconsider the vote.

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; import java.util.Objects; public class DirectoryContentAnalyserOne < // do not forgive to name your file private static final 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"); // update the path >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 : Objects.requireNonNull(currentDirOrFile.list())) < getDirectoryContent(currentDirOrFile + "\\" + currentFileOrDirName); >if (indentation.length() - 3 > 3) < indentation.delete(indentation.length() - 3, indentation.length()); >> > > 

Is there an error in this code? Should'nt getPrivateDirectoryContent() be replaced with getDirectoryContent()?

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! )