Author |
Topic: Recursion example? (Read 3950 times) |
|
Barukh
Uberpuzzler
Gender: 
Posts: 2276
|
 |
Recursion example?
« on: Jan 9th, 2014, 10:00am » |
 Quote  Modify
|
This is not a usual post...
I have decided to try tutorial assistance at the local technical University.
I am teaching "C language" course to non-CS students (by some reason, it's compulsory for almost all faculties here).
Next lesson is "Recursion", and I would like to give a good example of using recursion. Unfortunately, all the examples given in the slides may be easily - and more efficiently - implemented using simple loops.
But I am looking for an example where:
1. The problem formulation is not too difficult.
2. Solution using recursion is simpler, easier to implement than using loops.
3. The efficiency of recursion is of the same complexity as loop solution.
Under these restrictions, some problems naturally stated recursively - factorial, Fibonacci numbers, binomial coefficients - fall short.
Could you think of a good example?
Thanks!
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Recursion example?
« Reply #1 on: Jan 9th, 2014, 10:46am » |
Quote Modify
|
Two examples that readily come to mind are:
- Searching in a tree.
- Creating all permutations of a string.
NB, I think it's good to show an example like Fibonacci to teach them that recursion can be a horrible solution.
It'd also be good to teach them about tail recursion (which a compiler can optimize as a loop).
|
| « Last Edit: Jan 9th, 2014, 10:48am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Recursion example?
« Reply #2 on: Jan 12th, 2014, 10:57pm » |
Quote Modify
|
Towr, the example with generating all permutations of a string is excellent!
Many thanks!
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Recursion example?
« Reply #3 on: Jan 13th, 2014, 4:49am » |
Quote Modify
|
The same question has been asked here
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Recursion example?
« Reply #4 on: Jan 13th, 2014, 4:51am » |
Quote Modify
|
More seriously, another example would be an expression analyzer.
Or solving the towers of Hanoi from an arbitrary position.
Or solving a puzzle like sudoku with backtracking.
|
| « Last Edit: Jan 13th, 2014, 8:58am by Grimbal » |
IP Logged |
|
|
|
rloginunix
Uberpuzzler
Posts: 1029
|
|
Re: Recursion example?
« Reply #5 on: Jan 13th, 2014, 8:34am » |
Quote Modify
|
Practical
. and
.. tangible:
... producing a listing of a file system's directory:
.... all the files in the top level directory which may have
..... sub-directories each of which may have
...... sub-directories each of which may have
....... sub-directories ...
|
|
IP Logged |
|
|
|
rloginunix
Uberpuzzler
Posts: 1029
|
|
Re: Recursion example?
« Reply #6 on: Jan 13th, 2014, 10:33am » |
Quote Modify
|
Add the Tic-Tac-Toe puzzle to that.
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Recursion example?
« Reply #7 on: Jan 13th, 2014, 10:10pm » |
Quote Modify
|
And chess.
But with graph problems (which is what many games come down to) you must be careful, because you can reach the same state via multiple path, and you only want to deal with them once.
|
| « Last Edit: Jan 13th, 2014, 10:11pm by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
rloginunix
Uberpuzzler
Posts: 1029
|
|
Re: Recursion example?
« Reply #8 on: Jan 14th, 2014, 6:40pm » |
Quote Modify
|
Here's what I was talking about earlier. File system-based recursion, Korn shell style. This should mimick 'ls -lR' closely:
Code:
#!/bin/ksh
listMe()
{
echo ""
echo "`pwd`:"
ls -l
l="`ls -1 ./`"
if [ -z "${l}" ]
then
echo " This directory is empty."
else
for f in ${l}
do
if [ -d "${f}" ]
then
cd "${f}"
#
# Recursion.
#
listMe
cd ../
fi
done
fi
}
cd "$1"
listMe
|
|
|
|
IP Logged |
|
|
|
rloginunix
Uberpuzzler
Posts: 1029
|
|
Re: Recursion example?
« Reply #10 on: Jan 15th, 2014, 3:21pm » |
Quote Modify
|
In case you find it useful I've added two extras - stack frame numbers as they come and go and indentation to visualize the depth of recursion. For every new frame I shift the output one space over to the right:
#!/bin/ksh
indent()
{
N=$1
while [ ${N} -gt 1 ]
do
echo " \c"
let N="${N} - 1"
done
}
Echo()
{
indent $1
echo "$2"
}
Ls()
{
ls -l | while read ln
do
indent $1
echo ${ln}
done
}
listMe()
{
SFN=$1
echo ""
Echo ${SFN} "Stack frame ${SFN} IN."
Echo ${SFN} "`pwd`:"
Ls ${SFN}
l="`ls -1 ./`"
if [ -z "${l}" ]
then
Echo ${SFN} " This directory is empty."
else
for f in ${l}
do
if [ -d "${f}" ]
then
cd "${f}"
#
# Recursion.
#
let SFN="${SFN} + 1"
listMe ${SFN}
let SFN="${SFN} - 1"
cd ../
fi
done
fi
Echo ${SFN} "Stack frame ${SFN} OUT (`pwd`).\n"
}
cd "$1"
listMe 1
}
I also found it useful to comment out (or make optional) the call to the Ls() function in listMe(). This way the only factor that controls recursion - directories - show up in the output.
(Edit: changed "add" to "added".)
|
| « Last Edit: Jan 17th, 2014, 7:48am by rloginunix » |
IP Logged |
|
|
|
johngates
Newbie
Posts: 1
|
|
Re: Recursion example?
« Reply #11 on: Feb 25th, 2014, 10:19pm » |
Quote Modify
|
following is the program
#include "stdio.h"
void towers(int,char,char,char);
void towers(int n,char frompeg,char topeg,char auxpeg)
{ /* If only 1 disk, make the move and return */
if(n==1)
{ printf("\nMove disk 1 from peg %c to peg %c",frompeg,topeg);
return;
}
/* Move top n-1 disks from A to B, using C as auxiliary */
towers(n-1,frompeg,auxpeg,topeg);
/* Move remaining disks from A to C */
printf("\nMove disk %d from peg %c to peg %c",n,frompeg,topeg);
/* Move n-1 disks from B to C using A as auxiliary */
towers(n-1,auxpeg,topeg,frompeg);
}
main()
{ int n;
printf("Enter the number of disks : ");
scanf("%d",&n);
printf("The Tower of Hanoi involves the moves :\n\n");
towers(n,'A','C','B');
return 0;
}
for more latest technology go to apptuck.com
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print