Examples of Recursive functions?

This illustration is in English, rather than an actual programming language, but is useful for explaining the process in a non-technical way: A child couldn't sleep, so her mother told a story about a little frog, who couldn't sleep, so the frog's mother told a story about a little bear, who couldn't sleep, so bear's mother told a story about a little weasel ...who fell asleep. ...and the little bear fell asleep; ...and the little frog fell asleep; ...and the child fell asleep.

1 That's quite nice to read. – JosephStyons Oct 3 '08 at 14:35 1 Yeah, but where's the end condition/base case? ;-) – Joachim Sauer Feb 3 '09 at 13:53 1 @Joachim Weasel is always the base case, dude.

You know this! – Andres Jaan Tack May 4 '10 at 11:57 4 Also, this is beautiful. – Andres Jaan Tack May 4 '10 at 11:57 You don't see indented English often.

:-) – svick Sep 15 at 18:17.

Another couple of "usual-suspects" are Quicksort and MergeSort.

Bool isPalindrome(char* s, int len) { if(len.

The interpreter design pattern is a quite nice example because many people don't spot the recursion. The example code listed in the Wikipedia article illustrates well how this can be applied. However, a much more basic approach that still implements the interpreter pattern is a ToString function for nested lists: class List { public List(params object items) { foreach (object o in items) this.

Add(o); } // Most of the implementation omitted … public override string ToString() { var ret = new StringBuilder(); ret. Append("( "); foreach (object o in this) { ret. Append(o); ret.

Append(" "); } ret. Append(")"); return ret.ToString(); } } var lst = new List(1, 2, new List(3, 4), new List(new List(5), 6), 7); Console. WriteLine(lst); // yields: // ( 1 2 ( 3 4 ) ( ( 5 ) 6 ) 7 ) (Yes, I know it's not easy to spot the interpreter pattern in the above code if you expect a function called Eval … but really, the interpreter pattern doesn't tell us what the function is called or even what it does and the GoF book explicitly lists the above as an example of said pattern.).

Interestingly, any iteration can be expressed as a fold and fold can in turn be interpreted (pun intended) as a parametrizable interpreter for a programming language with just two commands element(e) and NIL, where the list is the program. Cool, huh? Found that interpretation here: Functional Programming for Beginners - Rúnar Óli Bjarnason - Boston Area Scala Enthusiasts.

– Jörg W Mittag Oct 8 at 16:16.

In my opinion, recursion is good to know, but most solutions that could use recursion could also be done using iteration, and iteration is by far more efficient. That said here is a recursive way to find a control in a nested tree (such as ASP. NET or Winforms): public Control FindControl(Control startControl, string id) { if (startControl.Id == id) return startControl if (startControl.Children.

Count > 0) { foreach (Control c in startControl. Children) { return FindControl(c, id); } } return null; }.

Such blanket statements are almost always false (yet another one ;-)). Use tail recursion and performance is on par with iteration. – Konrad Rudolph Sep 24 '08 at 14:19 Proponents of functional programming seem to prefer recursion whenever possible, and use the fact that tail recursion == iteration as an excuse.In the real world, recursion comes at a cost.

– Marcus Downing Sep 24 '08 at 16:09 holy! How did you get code off my development box? That is almost exactly character by character and even line spacing, a function I have in my own library.

– stephenbayer Sep 24 '08 at 16:36 stephen, I think we've all written that function more than once :) Konrad, even tail recursion has the added cost of pushing the function arguments to the stack once. – FlySwat Sep 24 '08 at 17:09 Jon, even iteration, when encapsulated in a function, “has the added cost of pushing the function arguments to the stack once. €?

So there. Additionally, there's function call inlining which also works for tail recursive functions. – Konrad Rudolph Sep 24 '087 at 8:47.

My personal favorite is Binary Search Edit: Also, tree-traversal. Walking down a folder file structure for instance.

Implementing Graphs by Guido van Rossum has some recursive functions in Python to find paths between two nodes in graphs.

My favorite sort, Merge Sort (Favorite since I can remember the algorithm and is it not too bad performance-wise).

Merge sort is awesome :) ... and also one of the few algorithms I actually remember! – anbanm Sep 24 '08 at 12:23.

The hairiest example I know is Knuth's Man or Boy Test. As well as recursion it uses the Algol features of nested function definitions (closures), function references and constant/function dualism (call by name).

From the world of math, there is the Ackermann function: Ackermann(m, n) { if(m==0) return n+1; else if(m>0 && n==0) return Ackermann(m-1, n); else if(m>0 && n>0) return Ackermann(m-1, Ackermann(m, n-1)); else throw exception; //not defined for negative m or n } It always terminates, but it produces extremely large results even for very small inputs. Ackermann(4, 2), for example, returns 265536 − 3.

In order to understand recursion, one must first understand recursion.

Recursive functions are great for working with recursively defined datatypes: A natural number is zero or the successor of another natural number A list is the empty list or another list with an element in front A tree is a node with some data and zero or more other subtrees Etc.

Factorial Traversing a tree in depth (in a filesystem, a game space, or any other case).

Actually, factorial is often better done using a loop. It's kind of a stupid, tho often used, example – Rik Sep 24 '08 at 12:36 It may perfrom better in a loop, but it is a well understood idea that easily expressed rescursively especially in languages with partial functions. – Steve g Sep 24 '08 at 13:13 So many common examples are actually loop-like, simply because the people who use functional languages seem to prefer recursion.In 'normal' programming languages, most things are better done as a loop, both for performance and for readable code.

– Marcus Downing Sep 24 '08 at 16:04.

Void rev(string s) { if (!s.empty()) { rev(s1..s. Length); } print(s0); } Understanding this helps understand recursion.

Like factorial, reversing a string is much more easily done with a loop. – Kip Sep 24 '08 at 13:39 Sure it is, but this question requested examples to illustrate recursion, and this example adds something not found in other examples. – Yuval F Dec 2 '08 at 7:24.

Here is a sample I posted on this site a while back for recursively generating a menu tree: Recursive Example.

How about anything processing lists, like: map (and andmap, ormap) fold (foldl, foldr) filter etc...

Translate a spreadsheet column index to a column name. It's trickier than it sounds, because spreadsheet columns don't handle the '0' digit properly. For example, if you take A-Z as digits when you increment from Z to AA it would be like going from 9 to 11 or 9 to 00 instead of 10 (depending on whether A is 1 or 0).

Even the Microsoft Support example gets it wrong for anything higher than AAA! The recursive solution works because you can recurse right on those new-digit boundries. This implementation is in VB.Net, and treats the first column ('A') as index 1.

Function ColumnName(ByVal index As Integer) As String Static chars() As Char = {"A"c, "B"c, "C"c, "D"c, "E"c, "F"c, "G"c, "H"c, "I"c, "J"c, "K"c, "L"c, "M"c, "N"c, "O"c, "P"c, "Q"c, "R"c, "S"c, "T"c, "U"c, "V"c, "W"c, "X"c, "Y"c, "Z"c} index -= 1 'adjust index so it matches 0-indexed array rather than 1-indexed column' Dim quotient As Integer = index \ 26 'normal / operator rounds. \ does integer division' If quotient > 0 Then Return ColumnName(quotient) & chars(index Mod 26) Else Return chars(index Mod 26) End If End Function.

Once upon a time, and not that long ago, elementary school children learned recursion using Logo and Turtle Graphics. en.wikipedia.org/wiki/Turtle_graphics Recursion is also great for solving puzzles by exhaustive trial. There is a kind of puzzle called a "fill in" (Google it) in which you get a grid like a crossword, and the words, but no clues, no numbered squares.

I once wrote a program using recursion for a puzzle publisher to solve the puzzles in order be sure the known solution was unique.

As others have already said, a lot of canonical recursion examples are academic. Some practical uses I 've encountered in the past are: 1 - Navigating a tree structure, such as a file system or the registry 2 - Manipulating container controls which may contain other container controls (like Panels or GroupBoxes).

A real-world example is the "bill-of-materials costing" problem. Suppose we have a manufacturing company that makes final products. Each product is describable by a list of its parts and the time required to assemble those parts.

For example, we manufacture hand-held electric drills from a case, motor, chuck, switch, and cord, and it takes 5 minutes. Given a standard labor cost per minute, how much does it cost to manufacture each of our products? Oh, by the way, some parts (e.g. The cord) are purchased, so we know their cost directly.

But we actually manufacture some of the parts ourselves. We make a motor out of a housing, a stator, a rotor, a shaft, and bearings, and it takes 15 minutes. And we make the stator and rotor out of stampings and wire, ... So, determining the cost of a finished product actually amounts to traversing the tree that represents all whole-to-list-of-parts relationships in our processes.

That is nicely expressed with a recursive algorithm. It can certainly be done iteratively as well, but the core idea gets mixed in with the do-it-yourself bookkeeping, so it's not as clear what's going on.

Here's a pragmatic example from the world of filesystems. This utility recursively counts files under a specified directory. (I don't remember why, but I actually had a need for something like this long ago...) public static int countFiles(File f) { if (f.isFile()){ return 1; } // Count children & recurse into subdirs: int count = 0; File files = f.listFiles(); for (File fileOrDir : files) { count += countFiles(fileOrDir); } return count; } (Note that in Java a File instance can represent either a normal file or a directory.

This utility excludes directories from the count. ) A common real world example would be e.g. FileUtils.deleteDirectory() from the Commons IO library; see the API doc & source.

I cant really gove you an answer,but what I can give you is a way to a solution, that is you have to find the anglde that you relate to or peaks your interest. A good paper is one that people get drawn into because it reaches them ln some way.As for me WW11 to me, I think of the holocaust and the effect it had on the survivors, their families and those who stood by and did nothing until it was too late.