Recursion without factorial, Fibonacci numbers etc

recursion

Almost every article I can find about recursion includes the examples of factorial or Fibonacci Numbers, which are:

Math
Useless in real life

Are there some interesting non-math code examples to teach recursion?

I'm thinking divide-and-conquer algorithms but they usually involve complex data structures.

Best Answer

Directory / File structures are the best example of a use for recursion, because everyone understands them before you start, but anything involving tree-like structures will do.

void GetAllFilePaths(Directory dir, List<string> paths)
{
    foreach(File file in dir.Files)
    {
        paths.Add(file.Path);
    }

    foreach(Directory subdir in dir.Directories)
    {
        GetAllFilePaths(subdir, paths)
    }
}

List<string> GetAllFilePaths(Directory dir)
{
    List<string> paths = new List<string>();
    GetAllFilePaths(dir, paths);
    return paths;
}

Related Solutions

Recursion – Is it ‘Divide and Conquer’ or ‘Code Reuse’

what are the "problem patterns" that call for the solution of recursion

I wouldn't say there's such a thing like a problem pattern for the use of recursion. Every function that can be implemented with recursion can also be implemented iteratively, often by pushing and popping a stack.

It's a matter of expression and also of performance. Iterative algorithms often times have a better performance and are easier to optimize. However, recursive algorithms benefit from a clearer expression and thus are often easier to read, understand and implement.

Some things even cannot be expressed without recursion, infinite lists for example. The so called functional languages heavily rely on recursion, as it's their natural way of expression. The saying is: "Recursive programming is functional programming done right".

is recursion a form of "divide & conquer" strategy or a form of "code reuse" -- or, is a design pattern in its own right

I would not call it a design pattern. It's a matter of expression. Sometimes a recursive expression is simply more powerful and more expressive and thus leads to better and cleaner code.

can you give us an example of a real world problem where recursion comes to mind as an immediate solution

Anything that needs to traverse trees will be properly expressed by a recursive algorithm.

Python – Check distance between all elements in a list of numbers in O(n*lg(n))

I guess you don't need this anymore, but since I realized gnasher's bump only after thinking about this, I'll leave some imho nicer code here anyway:

def check_distance(X, k):
    A = merge_sort(X)
    return all(b-a >= k for a, b in zip(A, A[1:]))

I'm interested in the teacher's solution. Did he just have this braindead sort and sweep in mind, or something more interesting?

Best Answer

Related Solutions

Recursion – Is it ‘Divide and Conquer’ or ‘Code Reuse’

Python – Check distance between all elements in a list of numbers in O(n*lg(n))

Related Topic