#### Do you have a question? Post it now! No Registration Necessary. Now with pictures!

## Re: recursive functions

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!

## Re: recursive functions

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

> 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

## Re: recursive functions

>

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

## Re: recursive functions

> 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

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

}

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

> 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

## Re: recursive functions

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

print count

sub count

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

}

example two:

#!/usr/bin/perl -w

$string = "test

print combine($string);

sub combine {

my @words = split /\n/, shift;

return @words unless @_;

my @combinations;

for my $word (@words) {

push @combinations => map { "$word $

}

@combinations;

}

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;

}

## Re: recursive functions

> 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

## Re: recursive functions

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

would be harder to visualize with the recursive routine ..

HTH

Regards

--

Abhinav

> 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

## Re: recursive functions

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

}

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

}

## Re: recursive functions

[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

## Re: recursive functions

>

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

## Re: recursive functions

>

> >

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

solved recursively, but are better treated otherwise.

Anno

> >

> > [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***besolved recursively, but are better treated otherwise.

Anno

## Re: recursive functions

> 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

## Re: recursive functions

>

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

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

## Re: recursive functions

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

## Re: recursive functions

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

## Re: recursive functions

<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

> 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

#### Site Timeline

- » FAQ 1.3 Which version of Perl should I use?
- — Next thread in » PERL Discussions

- » @platforms = (sort keys %prj_platforms) || (DEFAULT);
- — Previous thread in » PERL Discussions

- » s suffix question
- — Newest thread in » PERL Discussions

- » SSD partition alignment revisited
- — The site's Newest Thread. Posted in » Computer Hardware