recursive functions

Discussion in 'Perl Misc' started by steve_f, Aug 4, 2004.

  1. steve_f

    steve_f Guest

    I could never really wrap my mind around the concept
    of recursive functions. I'm not sure if this is the right
    place to ask...but if anyone can at least clue me in a
    bit, I would really appreciate it.
     
    steve_f, Aug 4, 2004
    #1
    1. Advertising

  2. steve_f

    Sam Holden Guest

    On Wed, 04 Aug 2004 08:59:12 -0400, steve_f <> wrote:
    > I could never really wrap my mind around the concept
    > of recursive functions. I'm not sure if this is the right
    > place to ask...but if anyone can at least clue me in a
    > bit, I would really appreciate it.


    A more general programming group might be better...

    A recursive function is a function which calls itself. To prevent
    inifinite recursion there needs to be at least one case in which
    the function doesn't call itself (often called the base case).
    Generally the function solves some part of the problem and calls
    itself in order to solve the smaller problem that remains. At some
    point the smaller problem is so small that the answer is known.

    For example here is a non-recursive function to count the number of
    strings with the value 'needle' in an array of strings:

    sub count_em {
    my $count = 0;
    for my $item (@_) {
    $count++ if $item eq 'needle';
    }
    return $count;
    }

    It simply looks at each element in the array (@_) and increments the count
    if it is 'needle'.

    This could also be done recursively.

    An obvious base case is the empty array that cleary contains 0 occurances
    of the string "needle".

    So just the base case would be:

    return 0 if @_ == 0;

    For a larger array we can can split it in two, the first element and the
    rest of the array. If the first element is "needle" then the answer is
    1 + <the number of occurances of "needle" in the rest of the array>, or
    just <the number of occurances of "needle" in the rest of the array> if
    the first element isn't "needle", in other words:

    sub count_em_recursive {
    return 0 if @_ == 0; # the base case

    my $item = shift @_; # solve part of the problem
    my $needle;
    if ($item eq 'needle') {
    $needle = 1;
    } else {
    $needle = 0;
    }

    return $needle + count_em_recursive(@_); # recurse on smaller problem
    }

    Obviously, this is a remarkably silly thing to do recursively (when
    using perl anyway). But examples often suffer from that problem.

    Recursion is something a lot of people (in my experience of teaching
    anyway) have trouble understanding. It is also one of those things that
    seems to "click", and then the person understands...

    It's just like "proof by induction" in maths - if you happen to have
    done that...

    Recursion is usually used with recursive data structures (such as trees) since
    a recursive function "maps" easily onto the data structure.

    [*]- yes I realise shift operates on @_ by default (in that context), and that
    this is actually a place where the &func; syntax is useful :) - but I
    suspect it would detract from the example...
    --
    Sam Holden
     
    Sam Holden, Aug 4, 2004
    #2
    1. Advertising

  3. steve_f

    steve_f Guest

    OK thanks, now I have two working examples. I took a year of calculus,
    but don't think I ever encountered "proof by induction".

    This concept has never really clicked for me. For example, I wouldn't
    recognize what type of problem would need a recursive solution.

    I know the concept is a function calls itself repeatedly until it
    runs out and now that there is a base case.

    example one:
    #!/usr/bin/perl -w
    @array = qw( test_1 test_2 test_3 );
    print count_em_recursive(@array);
    sub count_em_recursive {
    return 0 if @_ == 0; # the base case
    my $item = shift @_; # solve part of the problem
    my $needle;
    if ($item eq 'needle') {
    $needle = 1;
    } else {
    $needle = 0;
    }
    return $needle + count_em_recursive(@_); # recurse on smaller problem
    }

    example two:
    #!/usr/bin/perl -w
    $string = "test_1\ntest_2\ntest_3";
    print combine($string);
    sub combine {
    my @words = split /\n/, shift;
    return @words unless @_;
    my @combinations;
    for my $word (@words) {
    push @combinations => map { "$word $_" } combine(@_);
    }
    @combinations;
    }
     
    steve_f, Aug 4, 2004
    #3
  4. In article <>, "steve_f"
    <> wrote:

    > I could never really wrap my mind around the concept of recursive
    > functions. I'm not sure if this is the right place to ask...but if
    > anyone can at least clue me in a bit, I would really appreciate it.


    The absolute classic example of a recursive algorithm is the factorial
    function. This relies on the relationship

    n! = n * (n-1)!

    and the fact that

    1! = 1

    so the code pretty much writes itself ...

    #!/usr/bin/perl

    my $f = shift;
    print "$f! = ",factorial($f),"\n";

    sub factorial {
    my $n = shift;

    if ($n == 1) {
    # base case
    return 1;
    } else {
    return $n * factorial($n-1);
    }
    }

    HTH
    Rich
     
    Richard Gration, Aug 4, 2004
    #4
  5. steve_f

    Abhinav Guest

    steve_f wrote:
    > OK thanks, now I have two working examples. I took a year of calculus,
    > but don't think I ever encountered "proof by induction".
    >
    > This concept has never really clicked for me. For example, I wouldn't
    > recognize what type of problem would need a recursive solution.
    >


    Some other examples which might help visualize the idea would be

    1. Binary Search
    2. Factorial
    3. Tower of Hanoi problem
    4. Directory search of a file system
    5. Depth First Search (DFS) of a (binary) tree

    I have not mentioned fibonacci series in the list, because that *generally*
    would be harder to visualize with the recursive routine ..

    HTH

    Regards

    --

    Abhinav
     
    Abhinav, Aug 4, 2004
    #5
  6. steve_f

    Anno Siegel Guest

    steve_f <> wrote in comp.lang.perl.misc:
    > OK thanks, now I have two working examples. I took a year of calculus,
    > but don't think I ever encountered "proof by induction".


    Sounds unlikely. There are lots of propositions in elementary calculus
    that are best proved inductively. Also, induction is so important in
    all branches of mathematics that teachers tend to bring it up in any
    elementary course.

    > This concept has never really clicked for me. For example, I wouldn't
    > recognize what type of problem would need a recursive solution.


    If you have a problem that can't be solved immediately, one technique
    to find a solution is often called "Divide and Conquer". That means,
    split the problem into two or more sub-problems, so that a solution
    of the whole problem can be constructed when the subproblems are solved.
    The hope is that the sub-problems will be easier. The technique can
    then repeatedly be applied to the sub-problems, simplifying at each
    step until all remaining (sub-)problems are immediately solvable.

    It may happen that one or more subproblems have the same structure
    as the original problem. The subproblems may still be simpler than
    the original, for instance by having to deal with smaller numbers
    or fewer things.

    If that happens, it is an invitation to try a recursive solution.
    The advantage is that the sub-problem, having the same structure as
    the original, can again be split into sub-problems using the same
    technique again, until elementary cases are reached. If the sub-problems
    are unrelated to the original, new methods must be found at each level.

    > I know the concept is a function calls itself repeatedly until it
    > runs out and now that there is a base case.


    Strictly speaking, this is slightly too narrow. A function doesn't
    have to call itself to be recursive, it may call another function
    which calls another which, eventually, calls the first function again.
    Technically, a call to a function is recursive if another call to the
    same function hasn't returned yet.

    [examples snipped]

    Anno
     
    Anno Siegel, Aug 4, 2004
    #6
  7. steve_f

    Anno Siegel Guest

    Abhinav <> wrote in comp.lang.perl.misc:

    [recursion]

    > Some other examples which might help visualize the idea would be
    >
    > 1. Binary Search
    > 2. Factorial
    > 3. Tower of Hanoi problem
    > 4. Directory search of a file system
    > 5. Depth First Search (DFS) of a (binary) tree


    These are good examples, with exception of number 2, which is only popular.
    I have never quite understood why.

    Nothing in multiplying the first few numbers together particularly invites
    recursion, not any more than adding them up would. Calculating the number
    of permutations of n things (which happens to be n!) *is* a naturally
    recursive problem. Calculating factorials isn't.

    Anno
     
    Anno Siegel, Aug 4, 2004
    #7
  8. steve_f

    Anno Siegel Guest

    Richard Gration <> wrote in comp.lang.perl.misc:
    > In article <>, "steve_f"
    > <> wrote:
    >
    > > I could never really wrap my mind around the concept of recursive
    > > functions. I'm not sure if this is the right place to ask...but if
    > > anyone can at least clue me in a bit, I would really appreciate it.

    >
    > The absolute classic example of a recursive algorithm is the factorial
    > function. ...


    Classic only in the sense of mythology. Nothing about the factorial
    invites a recursive algorithm, and the recursive implementation has
    no advantages over an iterative one.

    Anno
     
    Anno Siegel, Aug 4, 2004
    #8
  9. steve_f

    steve_f Guest

    wow....I kind of wrote my own recursive function...
    well, I rewrote it from an example in some other
    language...

    #!c:\perl\bin\perl.exe -w

    $m = 5;
    $n = 10;

    print multiply_em($m, $n);

    sub multiply_em {
    my ($m, $n) = @_;
    if ($n == 1) {
    return $m;
    }
    return $m + multiply_em($m, $n - 1);
    }

    thanks everyone...it is begining to become clear to me.
    yes, my calculus was so long ago, but I think that is what
    makes perl attractive to me.

    ok...I think the trick is in the $n-1 ...so it is counting down as
    it is passing through the function almost like a for construction
    for x = 0, x < 10, x++

    here's the other list of examples:
    compute the power of x to the n, where x and n are both integers
    print the characters of a string in reverse order
    sum the numbers of an array of doubles
    print the items of a linked list, assuming a toString()method is defined for the item part of a Node
    find the minumum value in an array of ints
    sort an array using the strategy of the selection sort
    search through a sorted arrya using the strategy of the binary search

    hmmmm....!! ok, yes this post was off topic, I really should of found a
    programming group!
     
    steve_f, Aug 4, 2004
    #9
  10. steve_f

    steve_f Guest

    On Wed, 04 Aug 2004 12:09:50 -0400, steve_f <> wrote:

    >sub multiply_em {
    > my ($m, $n) = @_;
    > if ($n == 1) {
    > return $m;
    > }
    > return $m + multiply_em($m, $n - 1);
    >}


    yes, this is pretty much the same as:

    for $x = 1; $x < $n; $x++ {
    count += $m
    }
     
    steve_f, Aug 4, 2004
    #10
  11. In article <cer0qa$4um$-Berlin.DE>, "Anno Siegel"
    <-berlin.de> wrote:


    > Richard Gration <> wrote in comp.lang.perl.misc:
    >> The absolute classic example of a recursive algorithm is the factorial
    >> function. ...

    >
    > Classic only in the sense of mythology. Nothing about the factorial
    > invites a recursive algorithm, and the recursive implementation has no
    > advantages over an iterative one.
    > Anno


    But you have to agree it illustrates the concept of recursion well. A
    computer is not the ideal tool to convert celsius to fahrenheit either,
    yet I have written a few programs to do just that when learning a
    language. :)

    Rich
     
    Richard Gration, Aug 4, 2004
    #11
  12. steve_f wrote:

    > hmmmm....!! ok, yes this post was off topic, I really should of found a
    > programming group!


    To bring it back on-topic, then, you might want to have a look at
    O'Reilly's "Mastering Algorithms with Perl". A number of recursive
    algorithms are discussed in it.

    sherm--


    --
    Cocoa programming in Perl: http://camelbones.sourceforge.net
    Hire me! My resume: http://www.dot-app.org
     
    Sherm Pendley, Aug 4, 2004
    #12
  13. steve_f

    Anno Siegel Guest

    Richard Gration <> wrote in comp.lang.perl.misc:
    > In article <cer0qa$4um$-Berlin.DE>, "Anno Siegel"
    > <-berlin.de> wrote:


    > > Richard Gration <> wrote in comp.lang.perl.misc:
    > >> The absolute classic example of a recursive algorithm is the factorial
    > >> function. ...


    [...]

    > But you have to agree it illustrates the concept of recursion well. A


    The factorial example illustrates the *mechanics* of recursion. But so
    do summing up (instead of multiplying) the first integers, or counting
    the elements in a list, or a dozen tasks that can be done recursively,
    but are best done iteratively, in Perl and most other languages.

    It does nothing to help develop judgment of when recursion is an
    appropriate solution, and where it's only (possibly expensive)
    claptrap. In everyday programming, the most frequent question
    about recursion is whether to use it at all. The factorial
    example teaches the wrong decision.

    If you want a simple arithmetic example for a naturally recursive
    problem, use Euclid's algorithm.

    sub euclid {
    my ( $a, $b) = @_;
    $b ? euclid( $b, $a % $b) : $a;
    }

    > computer is not the ideal tool to convert celsius to fahrenheit either,


    Why on earth not? Would you prefer a slide-rule? It isn't used to
    its full capacity, for sure, but that's something else.

    > yet I have written a few programs to do just that when learning a
    > language. :)


    You weren't taught to do that recursively, I suppose :)

    Anno
     
    Anno Siegel, Aug 4, 2004
    #13
  14. steve_f

    thundergnat Guest

    Abhinav wrote:

    > 4. Directory search of a file system



    Heres something I had done at one point.
    This could be MUCH more efficiently done with File::Find
    but I wrote this to noodle around with recursion.

    Print a manifest of a directory tree with file sizes to a file
    $dir.mft.


    #!/usr/bin/perl
    use strict;
    use warnings;
    use Cwd;

    my $dir = $ARGV[0];
    die "You must specify a starting directory" unless $dir;
    $dir =~ m/[\\\/](\w+)[\\\/]?$/;
    die "Bad directory name: $dir" unless $1;
    my $name = $1.".mft";
    my $cwd = getcwd;
    my ($indent,$index,@mfst);
    my $space = '';

    mft($dir);

    chdir $cwd;
    open my $MFST, ">$name" or die "Could not open file $!";
    print $MFST "Manifest for $dir.\n\n";
    print $MFST @mfst;

    sub mft{
    my $dir = shift;
    $indent += 2;
    chdir $dir;
    my @list = glob("*");
    foreach my $file(@list) {
    if (-d $file){
    push @mfst, (' ' x $indent).$file."\n";
    mft($file);
    }else{
    push @mfst, (' ' x $indent).$space.$file.' '.
    (((-s $file)>1024) ?
    (sprintf "%.1f", (-s $file)/1024)."K\n" :
    (sprintf "%d", (-s $file))."B\n");
    }
    }
    $indent -= 2;
    chdir '..';
    }
     
    thundergnat, Aug 4, 2004
    #14
  15. steve_f

    Bill Smith Guest

    "Anno Siegel" <-berlin.de> wrote in message
    news:ceqvfh$3ot$-Berlin.DE...
    > Abhinav <> wrote in comp.lang.perl.misc:
    >
    > [recursion]
    >
    > > Some other examples which might help visualize the idea would be
    > >
    > > 1. Binary Search
    > > 2. Factorial
    > > 3. Tower of Hanoi problem
    > > 4. Directory search of a file system
    > > 5. Depth First Search (DFS) of a (binary) tree

    >
    > These are good examples, with exception of number 2, which is only

    popular.
    > I have never quite understood why.
    >
    > Nothing in multiplying the first few numbers together particularly

    invites
    > recursion, not any more than adding them up would. Calculating the

    number
    > of permutations of n things (which happens to be n!) *is* a naturally
    > recursive problem. Calculating factorials isn't.
    >




    Recursion provides a way to SPECIFY many functions (including all of
    these examples) briefly, yet completely. Computer languages, which
    support recursion, allow us to implement these directly without the
    effort to find and validate a non-recursive solution. We usually pay a
    heavy price in both speed and memory for this convenience.

    The factorial function belongs on this list because the beginner can
    evaluate the pros and cons of both methods.

    Bill
     
    Bill Smith, Aug 5, 2004
    #15
  16. steve_f

    Anno Siegel Guest

    Bill Smith <> wrote in comp.lang.perl.misc:
    >
    > "Anno Siegel" <-berlin.de> wrote in message
    > news:ceqvfh$3ot$-Berlin.DE...
    > > Abhinav <> wrote in comp.lang.perl.misc:
    > >
    > > [recursion]
    > >
    > > > Some other examples which might help visualize the idea would be
    > > >
    > > > 1. Binary Search
    > > > 2. Factorial
    > > > 3. Tower of Hanoi problem
    > > > 4. Directory search of a file system
    > > > 5. Depth First Search (DFS) of a (binary) tree

    > >
    > > These are good examples, with exception of number 2, which is only

    > popular.
    > > I have never quite understood why.
    > >
    > > Nothing in multiplying the first few numbers together particularly

    > invites
    > > recursion, not any more than adding them up would. Calculating the

    > number
    > > of permutations of n things (which happens to be n!) *is* a naturally
    > > recursive problem. Calculating factorials isn't.
    > >

    >
    >
    >
    > Recursion provides a way to SPECIFY many functions (including all of
    > these examples) briefly, yet completely.


    Why would anyone want to specify the factorial recursively? It's the
    product of the first n natural numbers.

    > Computer languages, which
    > support recursion, allow us to implement these directly without the
    > effort to find and validate a non-recursive solution. We usually pay a
    > heavy price in both speed and memory for this convenience.


    If the specification isn't recursive, there's no need to find a
    non-recursive solution.

    > The factorial function belongs on this list because the beginner can
    > evaluate the pros and cons of both methods.


    It belongs on a second list that demonstrates problems that *can* be
    solved recursively, but are better treated otherwise.

    Anno
     
    Anno Siegel, Aug 5, 2004
    #16
  17. steve_f

    Tom Regner Guest

    Re: recursive functions [Silly Joke]

    steve_f wrote:
    > I could never really wrap my mind around the concept
    > of recursive functions.

    That's because:
    To Know Recursion, You Must First Know Recursion...

    sorry, couldn't resist
    ;)
    --
    Dievision GmbH | Kriegerstrasse 44 | 30161 Hannover
    Telefon: (0511) 288791-0 | Telefax: (0511) 288791-99
    http://www.dievision.de
     
    Tom Regner, Aug 5, 2004
    #17
  18. In article <cercpd$bn1$-Berlin.DE>, "Anno Siegel"
    <-berlin.de> wrote:
    <SNIP>
    > In everyday programming, the most frequent question about recursion is
    > whether to use it at all. The factorial example teaches the wrong
    > decision.


    Fair point. Agreed.

    > If you want a simple arithmetic example for a naturally recursive
    > problem, use Euclid's algorithm.
    >
    > sub euclid {
    > my ( $a, $b) = @_;
    > $b ? euclid( $b, $a % $b) : $a;
    > }
    >


    That's beautiful ... noted for future reference

    >> computer is not the ideal tool to convert celsius to fahrenheit

    either,
    >
    > Why on earth not?


    the overkill factor ... put another way ... (possibly expensive) claptrap ? ;-)

    > Would you prefer a slide-rule? It isn't used to its


    well, when I wrote the above comment, a long strip of paper with 2
    columns of marks with numbers next to them was one tool which came to
    mind!

    >> yet I have written a few programs to do just that when learning a
    >> language. :)

    > You weren't taught to do that recursively, I suppose :)


    The mind boggles ... ;-)

    Rich
     
    Richard Gration, Aug 5, 2004
    #18
  19. steve_f

    steve_f Guest

    I just want to thank everyone one more time...very interesting
    discussion...now I have to examine my programming and
    see if any problems require a recursive solution ;-)
     
    steve_f, Aug 9, 2004
    #19
  20. steve_f

    David Combs Guest

    In article <>,
    Sherm Pendley <> wrote:
    >steve_f wrote:
    >
    >> hmmmm....!! ok, yes this post was off topic, I really should of found a
    >> programming group!

    >
    >To bring it back on-topic, then, you might want to have a look at
    >O'Reilly's "Mastering Algorithms with Perl". A number of recursive
    >algorithms are discussed in it.


    I think he'd be a lot better off getting one or several
    standard algorithms texts --- over the last 20 or so years there's
    been so very many good ones!

    Go to amazon and search, I guess, for "algorithms" or the like,
    and read the reader-reviews.

    David
     
    David Combs, Aug 25, 2004
    #20
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. gpi5
    Replies:
    1
    Views:
    1,140
    Mike Treseler
    Nov 9, 2004
  2. Xiangliang Meng
    Replies:
    1
    Views:
    1,613
    Victor Bazarov
    Jun 21, 2004
  3. dmattis

    Recursive Functions

    dmattis, Oct 27, 2003, in forum: C Programming
    Replies:
    64
    Views:
    1,594
    Nudge
    Nov 2, 2003
  4. n00m
    Replies:
    12
    Views:
    1,116
  5. vamsi
    Replies:
    21
    Views:
    2,085
    Keith Thompson
    Mar 9, 2009
Loading...

Share This Page