Possible Duplicates:
Real-world examples of recursion
Examples of Recursive functions
I see that most programming language tutorial teach recursion by using a simple example which is how to generate fibonacci sequence, my question is, is there another good example other than generating fibonacci sequence to explain how recursion works?
The classic is the binary tree search:
def findval (node,val):
if node == null:
return null
if node.val = val:
return node
if node.val > val:
return findval (node.left,val)
return findval (node.right,val)
findval (root,thing_to_find)
That may be a little more complex than a simple formula but it's the "bread and butter" use of recursion, and it illustrates the best places to use it, that where the recursion levels are minimised.
By that I mean: you could add two non-negative numbers with:
def add (a,b):
if b == 0:
return a
return add (a+1,b-1)
but you'd find yourself running out of stack space pretty quickly for large numbers (unless the compiler optimised tail-end recursions of course, but you should probably ignore that for the level of teaching you're concerned with).
The other answers mention various algorithms, which is completely fine, but if you want a bit more "concrete" example, you could list all files in some directory and its subdirectories. The hierarchical file system is a well-known example of a recursive (tree) structure, and you could show depth-first and breadth-first search using this concrete example.
My favourite example for recursion is the Towers of Hanoi: To move a stack of pieces from pole A to pole B, you move everything above the lowest piece to the pole that is not A or B, then move the lowest piece to B, and then you move the stack that you put on the "helper pole" on top of the lowest piece. For the first and third step, you follow this instruction recursively. See the link for a longer explanation :)
Check for a palyndrome:
bool recursivePalindrome(std::string str, unsigned int index = 0) {
if (index > str.length()/2) return true;
else if (str[index] == str[str.length()-index-1])
return recursivePalindrome(str, ++index);
else return false;
}
Or on a less serious note :)
void StackOverflow()
{
StackOverflow();
}
How about finding factorial.
int GetFactorial(int n )
{
if ( n==0) return 1;
return n*GetFactorial(n-1);
}
The idea is, factorial is defined recursively as the product of n and factorial of (n-1). And from recursive definition, you get your recursion.
Traversing the folder hierarchy of a directory tree as part of a file system is a good real-world example. Look into this SO post for a C++ example:
Merge sort is a pretty good example of an algorithm that is easier to read and understand when implemented recursively.
Here's a little high-level pseudocode version of Merge Sort:
def merge_sort(List sortlist)
if sortlist.length <= 1 return sortlist
split sortlist into leftlist and rightlist
return merge(merge_sort(leftlist), merge_sort(rightlist))
def merge(List leftlist, List rightlist)
while(leftlist and rightlist not empty)
compare leftlist.first to rightlist.first
pop lowest value off its list and append to resultlist
append any remains of leftlist onto resultlist
append any remains of rightlist onto resultlist
return resultlist
An iterative version of this is would be much more complicated to write and to visualise.
================
The example I use for demonstrating the simple power of recursion is recursive file processing in a directory tree.
Here is a C# example
void ProcessFiles( string sFolder )
{
foreach( string f in Directory.GetFiles( sFolder ) )
{
DoSomethingTo( f );
}
foreach( string d in Directory.GetDirectories( sFolder ))
{
ProcessFiles( d );
}
}
There are several samples:
T(n) = Sum(T(i)*T(n-i)) for all 1 <= i < n
A(x,y) = y+1 (if x = 0)
A(x,y) = A(x-1,1) (if y=0)
A(x,y) = A(x-1, A(x,y-1)) otherwise.
Finding Hamiltonian Path problem
factorial.
and you can see wiki page for other references.
Good examples of recursion are often related to cases where underlying data structure or the problem itself is recursive : trees, graphs, algorithms using divide and conquer approach (like many sorts), parser of recursive grammars (like common arithmetic expresions), find strategy for chess-like two players games (for a simple exemple consider Nim), combinatory problems, etc.
Try recursive binary search: http://www.fredosaurus.com/notes-cpp/algorithms/searching/rbinarysearch.html
Or a recursive quick sort: http://www.dreamincode.net/forums/topic/72311-recursive-quicksort-algorithm/
These are just two small example in a vast world of recursive functions.
Evaluation of arithmetic expressions can be done recursively or iteratively using a stack. It can be quite instructive to compare the two approaches.
My mother-in-law took an introductory course in C. She had a homework problem, something like:
You have a bar of metal (length len), and a number of orders (n) to cut the metal into various lengths. You want to maximize the amount of metal being used, but cannot exceed the overall length.
The instructor suggested iterating from 1 to 2**n in binary, excluding an order if its corresponding bit were 0 and including an order if its bit were 1, while keeping track of the maximum sum. His proposal would run in polynomial time.
Another solution exists using a recursive knapsack algorithm. You can iterate down from len to 1 and do a depth-first search to recursively find the sum of lengths.
A different area in which I have used recursion was for Huffman coding (for compressing a string), but this does not have the intuitive feel of the knapsack problem.
Recursion is a wonderful concept that is radically different. Best wishes in learning or teaching it.
Ackermann function:
/* undefined if m and n are negative */
uint32 ackermann( uint32 m, uint32 n )
{
if( m < 0 && n < 0 ) { exit(1); /* invalid m and n */ }
if( m == 0 ){ return n + 1; }
if( m > 0 && n == 0 ){ return ackermann( m - 1, 1 ); }
if( m > 0 && n > 0 ){ return ackermann( m - 1, ackermann(m, n - 1) ); }
}
The multiple comparisons of m > 0 are redundant (and can be simplified). Leaving them as-is, however, shows the standard definition of the Ackermann function.
But one does not have to go so far off the mathematical edge to find interesting recursive functions other than the Fibonnaci numbers.
You have the greatest common denominator (GDC) function, quicksort and the always typical binary search algorithm.
Anything which has a hierarchy. For example listing all the employees beneath your boss.
Recursion finds its fundations in mathematical induction, and should be taught as such.
Defining functions by induction can be exposed clearly with list processing. There are many things to say about fold for instance.
Then, move on to trees.
It's not C++, obviously, but the concept is sound:
PHP recursively traversing nested multidimensional arrays:
public function recurse_me($collection) {
foreach ($collection as $value) {
if (is_array($value)) {
$this->recurse_me($value);
} else {
// process value.
}
}
}
I remember that I understood recursion by writing a programm, that searches for word ladders. In a given dictionary.
The academic example is the factorial
n!
calculum. In real life, you get math libs.
There are sorting algorithms that rely on recursion.
And then, there's the binary search that is implemented with recursion.
Heap sort is also a good example. You can read about it in "Introduction to Algorithms" by Cormen, Rivest and others. Great book, I hope you'll find a lot of interesting there.
Lots of operations on linked-node type structures can be recursive. Others have mentioned BSTs, but if you don't want to have to explain what those are, consider searching for the highest value in a linear, unsorted list:
int MaxValue(Node node)
{
if (node == null)
return 0;
if (node.Next == null)
return node.Value;
int maxNext = MaxValue(node.Next);
return node.Value > maxNext ? node.Value : maxNext;
}
Lists (in this case, linked lists) are very easy to explain in real-world terms; your audience doesn't even have to have a programming background. You can simply describe it as a group of unsorted boxes, or a list of numbers.
