recursive Pythagorian triples

[Ed]

On Mar 16, 2:13 am, George Mpouras

[ much snipped ]

Did you find any missing triplet ?

The code does not produce, say, 9,12,15 (nor does it produce
12,9,15). See my other post about iterating over a multiplier (the k
value described in the wiki article).

Ed

 

[Peter J. Holzer]

Neither do I, which was the point of the post!

"Neither do I" or "Neither did I"?

It is trivial to convert a loop into recursion. I think my first answer
to your posting illustrated that. If you still don't understand it, feel
free to ask (as a followup to that posting).

hp

 

[Peter J. Holzer]

On Mar 16, 2:13 am, George Mpouras

[ much snipped ]

Did you find any missing triplet ?

I was going to reply that for $iterator->(4) it is apparent that many
triplets are missing and even for $iterator->(8), which produces
triplets with some values > 100 some values < 100 are still missing but

The code does not produce, say, 9,12,15 (nor does it produce
12,9,15).

this is a much better example, because it shows that there are some
triplets that the code can never produce parameter no matter how large
the parameter of $iterator is.

Because it is clear that the code can never produce 12,9,15 (the second
number is 2*$i*$j, so it must be even and 9 is not even) and for
9,12,15, the second term can only be produced by $i=3 and $j = 2, which
produces

$i**2 - $j**2 = 9 - 4 = 5
2 * $i * $j = 2 * 3 * 2 = 12
$i**2 + $j**2 = 9 + 4 = 13

which is not 9,12,15. So the code can never produce 9,12,15, no matter
which parameter $iterator is called.

Q.E.D.

See my other post about iterating over a multiplier (the k value
described in the wiki article).

Yup.

hp

 

[Xho Jingleheimerschmidt]

pythag(N) ->
[{A,B,C} ||
A<- seq(1,N),
B<- seq(1,N),
C<- seq(1,N),
A + B + C =< N,
(A * A) + (B * B) =:= C * C].

that's not recursive. that's a list comprehension.

Yes, it's a list comprehension. My question was, can you write a
Pythagorean triple function in Perl using recursion?

The above non-recursive example is what you gave to explain why you
wanted a recursive version in Perl. If we are not to assume that you
are just babbling incoherently, then the most reasonable assumption is
that you for some reason thought the above was recursive. Otherwise
using it as an example is just bizarre.


Xho

 

[George Mpouras]

unfortunately ... and can not be saved

 

[ccc31807]

The above non-recursive example is what you gave to explain why you
wanted a recursive version in Perl.  If we are not to assume that you
are just babbling incoherently, then the most reasonable assumption is
that you for some reason thought the above was recursive.  Otherwise
using it as an example is just bizarre.

You missed the point. I didn't mention the Erlang script to begin with
because it wasn't relevant to the question. I only mentioned it in the
context of providing an explanation of the original post. Perl doesn't
have list comprehensions, as far as I know, so you are correct in that
asking for a Perl script for finding Pythagoriean triples would indeed
be bizarre. But that wasn't the point.

The point was -- Can you find Pythagorean triples in Perl using
recursion? If you want a generalization, how do you solve a problem
that calls for triple recursion. PJH provided one solution that I
didn't like, but the next day I spend almost the entire day trying to
better it, and I failed. I'm not convinced that it can't be done in a
simpler way, but I don't think I can do it.

To make a larger point, Paul Graham has pointed out that different
languages are different, plugging Lisp. MJD showed how to write Perl
using Lisp-like constructs. Someone, I don't remember who, commented
that Perl can do everything Lisp can do except for Lisp macros.
Several years ago, Time Bray authored a famous blog attempted to use
Erlang to construct a database application, and concluded that Erlang
wasn't suited for the job, yet CouchDB uses Erlang.

And please don't point out that Erlang is derived from Prolog, not
Lisp. I know that. I also know that Lisp has iterative constructs, but
Erlang doesn't. The tie to Erlang was that the particular example used
list comprehensions, and I wondered how you could use Perl to do the
same kind of job, and recursion was as close as i could come to
Erlang's list comprehensions.

In one sense, this thread is simply an idle conversation, something
that you kick around in the break room. In another sense, discussing
how a particular algorithm can be implemented in Perl (or any other
language) is the kind of thing that 'sharpens the axe.'

If you think it's 'incoherent babble' you are free to ignore the
thread. If you think you can code a recursive Pythagorean triple
finder in Perl, you are welcome to try.

CC.

 

[George Mpouras]

Well it would be trivial (and opintless) to express
the nested loops in a recursive form. Would that satisfy
your request>

BugBear

# I have it !

&MySelf;

sub MySelf {
print ++$_[0]."\n";
4==$_[0] ? exit : &MySelf
}

 

[Jürgen Exner]

Yes, it's a list comprehension. My question was, can you write a
Pythagorean triple function in Perl using recursion?

Can you write it using a loop? Then yes, you can write it using
recursion because any loop can trivially be transformed into a recursion
by very basic program transformation.

WHILE (cond) {
body}

becomes

do_loop

FUNC do_loop {
if ( cond) {
body
do_loop
}
}

Oh, and before you ask: yes, any other loop form can be transformed into
a while loop.

What do students learn in computer science today?

I understand recursion as solving a problem by calling either directly
or indirectly the original function with a smaller set of the original
data until it returns on some base case.

Not necessarily a smaller set of data but there must exist some function
from data to natural numbers where the value will decrease with each
recursive call. This is called the termination function. It doesn't have
to reach 0, but it must become smaller. Otherwise you cannot guarantee
that the recursion will terminate.

jue

 

[ccc31807]

Well it would be trivial (and opintless) to express
the nested loops in a recursive form. Would that satisfy
your request>

First of all, I'm not very good at recursion, so this is a learning
exercise for me. My apologies if this offends anyone.

The first thing in writing a recursive function is to identify a base
case. For example, to find the length of a list, you start with the
base case of an empty list, the length of which is zero. Using Erlang
simply for the sake of syntax, you would write it like this:
list_len([]) -> 0;

The second thing is to identify the next smaller case after the
original argument, which is the original list minus one. The entire
function looks like this:
list_len([]) -> 0;
list_len([H|T]) -> 1 + list_len(T).

The fibonacci function is a double recursion in that you recurse down
two paths. This is a trivial implementation, without an accumulator,
and is not efficient, but it shows the double recursion:
fib(0) -> 1;
fib(1) -> 1;
fib(N) -> fib(N-1) + fib(N-2).

Now, my question is, how do you write a triple recursive IN PERL, for
example, to find Pythagorean triples?

CC.

 

[Willem]

ccc31807 wrote:
) Now, my question is, how do you write a triple recursive IN PERL, for
) example, to find Pythagorean triples?

As a counter question:
How would you write a *RECURSIVE* pythagorean triples in Erlang ?

Pythagorean triples is simply not a problem that is suitable for recursion.


SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

 

[Xho Jingleheimerschmidt]

If you think it's 'incoherent babble' you are free to ignore the
thread. If you think you can code a recursive Pythagorean triple
finder in Perl, you are welcome to try.

sub crap {
return crap($_[0]-1) if ($_[0]>0);
return non_recursive_code_that_does_the_job();
}

Xho

 

[Jürgen Exner]

ccc31807 wrote:
) Now, my question is, how do you write a triple recursive IN PERL, for
) example, to find Pythagorean triples?

I have no idea what a triple recursive is supposed to be ...

Pythagorean triples is simply not a problem that is suitable for recursion.

Really? This works for me:

use strict; use warnings;
sub is_square{
my ($x) = @_;
my $sq = sprintf("%u", sqrt($x));
if (($sq * $sq) == $x) {
return $sq;
} else {
return 0;
}
}

sub doit{
my ($a, $b) = @_;
exit if $b > 1000; #artifical termination of endless recursion
if ($a <= $b) {
my $c = is_square($a*$a + $b*$b);
print "($a, $b, $c)\n" if $c;
doit($a+1, $b);
} else {
doit(1, $b+1);
}
}

doit(1,1);

The only tricky part was to find a function that tests if a number is
the square of natural number. I am sure there are better ways but this
works.
And because this whole recursion is a tail recursion you can trivially
rewrite it into using only global variables, thus probably saving quite
some memory:

my ($a, $b, $c);
sub doit{
exit if $b > 1000; #artifical termination of endless recursion
if ($a <= $b) {
$c = is_square($a*$a + $b*$b);
print "($a, $b, $c)\n" if $c;
$a++;
doit();
} else {
$b++; $a=1;
doit();
}
}

$a = $b = 1;
doit();



jue

 

[Peter J. Holzer]

You missed the point. I didn't mention the Erlang script to begin with
because it wasn't relevant to the question. I only mentioned it in the
context of providing an explanation of the original post.

Unfortunately you didn't explain anything. Maybe you meant to write "I
came upon this non-recursive Erlang program, and I wondered why it
wasn't recursive, since Erlang programmers are normally very fond of
recursion. So I tried to come up with a recursive solution myself and
failed". But you didn't write that. Instead you just posted the script,
which left us to decide between the two alternatives Xho mentioned.

Perl doesn't have list comprehensions, as far as I know,

I don't know Erlang, but if the explanation at
http://en.wikibooks.org/wiki/Erlang_Programming/List_Comprehensions is
correct, the Perl equivalent is "map". (And someone already posted a
Perl program using map)

so you are correct in that asking for a Perl script for finding
Pythagoriean triples would indeed be bizarre. But that wasn't the
point.

Huh? How is asking for a Perl script for finding Pythagorean triples
bizarre? That's a very simple problem and you provided an adequate
solution in the very first posting in thread. It can be solved in any
turing-complete programming language and probably one of the most
popular exercises in introductory programming courses.

Xho found it bizarre that you provided a non-recursive Erlang program as
the reason for wanting to write a recursive Perl program. There are
programming languages in which the most natural way to implement an
algorithm is recursive. Perl isn't one of them.

The point was -- Can you find Pythagorean triples in Perl using
recursion?

The answer is of course: Yes, trivially.

If you want a generalization, how do you solve a problem
that calls for triple recursion. PJH provided one solution that I
didn't like, but the next day I spend almost the entire day trying to
better it, and I failed. I'm not convinced that it can't be done in a
simpler way, but I don't think I can do it.

The algorithm is so simple that there aren't many possible variations,
so I doubt you'll find a simpler recursive implementation of the same
algorithm.

You can of course change the algorithm (as George and Jürgen did) and
that may be faster, but not necessarily simpler.

And please don't point out that Erlang is derived from Prolog, not
Lisp. I know that. I also know that Lisp has iterative constructs, but
Erlang doesn't. The tie to Erlang was that the particular example used
list comprehensions, and I wondered how you could use Perl to do the
same kind of job, and recursion was as close as i could come to
Erlang's list comprehensions.

Ah, that explains it. Well, nobody understood that because nobody thinks
that recursion the closest thing Perl has to list comprehension. Map
seems to be almost equivalent (given the rather large differences
between Perl and Erlang in general), and even a plain loop is closer,
IMHO.

hp

 

[Jürgen Exner]

Going back to the root of this mega-thread

Pythagorian triples are integers that form the sides of a right
triangle, e.g., 3, 4, 5. I've posted an iterative version below for
all triples less than 100.

#! perl
use strict;
use warnings;
print "Pythagorian triples\n\n";
for(my $i = 1; $i < 101; $i++) {

Usually written and easier to read as
foreach my $i (1..100) {

{
for(my $j = 1; $j < 101; $j++) {
for(my $k = 1; $k < 101; $k++) {
print "$i - $j - $k\n" if ($i * $i + $j * $j) == ($k * $k);
}
}
}
exit(0);

I'm having trouble coming up with a
recursive version. Any ideas?

Trivial program transformation:

print "Pythagorian triples\n\n";
my ($i, $j, $k) = (1,1,1);
sub phyt{
print "$i - $j - $k\n" if ($i * $i + $j * $j) == ($k * $k);
if ($k < 101) {
if ($j <101) {
if ($i <101) {
$i++; phyt();
} else {
$i=1; $j++; phyt();
}
} else {
$i=1; $j=1; $k++; phyt();
}
}
}

phyt();
exit 0

How to get there? First transform each for loop into a while loop. Then
use the well-known program transformation from while loops into tail
recursion. And then a little bit of cleanup. Trivial, really.

jue

 

[Jürgen Exner]

In the past 2 days I posted 3 different, exclusively recursive versions.
Not to mention the generic program transformation rule which allows you
to transform any loop into a recursion. This is quite basic CS stuff.

Does that satisfy your requirements?

jue