wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Recursion example?
        
(Message started by: Barukh on Jan 9^th, 2014, 10:00am)

Title: Recursion example?
Post by Barukh on Jan 9^th, 2014, 10:00am

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!

Title: Re: Recursion example?
Post by towr on Jan 9^th, 2014, 10:46am

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

Title: Re: Recursion example?
Post by Barukh on Jan 12^th, 2014, 10:57pm

Towr, the example with generating all permutations of a string is excellent!

Many thanks!

Title: Re: Recursion example?
Post by Grimbal on Jan 13^th, 2014, 4:49am

The same question has been asked here (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_cs;action=display;num=1389290452)

Title: Re: Recursion example?
Post by Grimbal on Jan 13^th, 2014, 4:51am

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.

Title: Re: Recursion example?
Post by rloginunix on Jan 13^th, 2014, 8:34am

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

Title: Re: Recursion example?
Post by rloginunix on Jan 13^th, 2014, 10:33am

Add the Tic-Tac-Toe puzzle to that.

Title: Re: Recursion example?
Post by towr on Jan 13^th, 2014, 10:10pm

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.

Title: Re: Recursion example?
Post by rloginunix on Jan 14^th, 2014, 6:40pm

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

Title: Re: Recursion example?
Post by Grimbal on Jan 15^th, 2014, 9:28am

Or computing the Ackerman function. ::)
https://en.wikipedia.org/wiki/Ackermann_function

Title: Re: Recursion example?
Post by rloginunix on Jan 15^th, 2014, 3:21pm

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

Title: Re: Recursion example?
Post by johngates on Feb 25^th, 2014, 10:19pm

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