#1
  1. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Oct 2013
    Posts
    37
    Rep Power
    2

    Help with perl program


    This is not my first time posting this problem on this forum. Unfortunately, I am still stuck on this problem, and I just can't figure it out. Not looking to get an answer, just looking to see where I am making my mistake, I do believe I have made some progress. I know what I want to do, I just don't think I have the synthax to do so. Basically, my professor has given all of us students a recursion formula to calculate the pascal's triangle entry on the ith row and jth column.

    I don't know how many of you are familiar with this, but it is like this
    p(i,j) = p($i - $j + 1)/($j) * (p(i-1,j-1). So say I wanted to calculate the entry on row 5 column 3, it would be (5-1+1)/1 *(5-2+1)/2* (5 - 3 + 1)/3. So basically, it's like a multiplication of all the previous products. The math part is easy.

    The tough part comes when I want to put a code to this effect. Observe mines :

    my $j = <STDIN>;

    $count = 1;

    $p = ($i - $count + 1)/($count);

    if ($j > $i ) {
    print "Your column length must not be larger than your row
    length";

    }else {
    until ($count == $j ) {
    $p = ($i - $count + 1)/($count)*$p;
    $count++;
    }
    print "\n$p";
    }


    Is there any way I can save the first product, and than when the loop reiterates with a count + 1 I can multiply that new count's product by the previous?
  2. #2
  3. !~ /m$/
    Devshed Specialist (4000 - 4499 posts)

    Join Date
    May 2004
    Location
    Reno, NV
    Posts
    4,264
    Rep Power
    1810
    The math seems a bit off, but this seems close to what you are asking for:

    Code:
    my $count = 1;
    
    my $p = ($row - $count + 1)/$count;
    
    while (++$count <= $col ) {
    	$p *= ($row - $count + 1)/$count;
    }
    
    print "P: $p\n";
    Maybe it will help. It's not recursive however; it's just a simple loop.
  4. #3
  5. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Oct 2013
    Posts
    37
    Rep Power
    2
    Bro, I love you so much right now.

    That operator '*=' is what I was missing, and now my program works perfectly.
  6. #4
  7. No Profile Picture
    Contributing User
    Devshed Novice (500 - 999 posts)

    Join Date
    Jun 2012
    Location
    Paris area, France
    Posts
    842
    Rep Power
    496
    Hi,

    your program is definitely not recursive. So if your professor asked for a recursive program, then you need a complete rewrite.

    If you want to have a recursive program, then you need to define a function and that function has to call itself (each time with different values) until a certain condition is reached. I have already explained this to you in details before and I even provided you with a recursive program to compute the binomial coefficients (in this post: http://forums.devshed.com/perl-programming-6/need-help-with-a-loop-program-953470.html, post # 7).

    This is part of what I wrote at the time:

    Let's set up the Pascal triangle:
    1
    1 1
    1 2 1
    1 3 3 1
    1 4 6 4 1

    Suppose we need to compute pascal(5, 3), whose value is 6 (i.e. 5th row, 3rd column). We have: pascal (5, 3) = pascal (4, 2) + pascal (4,3) = 3 + 3. But, of course, you don't know at this point that these two values are both 3. so you need to compute them. And so on until you reach a known value.

    So the mathematical rules are as follows:
    - pascal (1, 1) = 1;
    - pascal (i, j) = pascal (i-1, j-1) + pascal (i-1, j);
    - With an additional rule: if j gets to 0, set it to 1.

    If you have learned subroutines and recursion, this can be done in about 4 lines of code.
    So, you define a function, named pascal and, in it, just apply the mathematical rules above. To make things easier, you can apply some other properties of the Pascal triangle:
    - pascal (1, j) = 1 for any value of j
    - pascal (i, j) = 1 if i == j
    (although you probably need only the first one)

    If you decide to use the recursive program I provided to you at the time, well, it is up to you, but remember that I intentionally left a small bug (namely that it returned pascal (i + 1, j) instead of pascal (i, j), if I remember correctly). This should be very easy to fix. However, I would strongly advise to look at it to understand how recursion works in this case, and then to set out to re-write something by yourself along the same lines. You will learn much more by doing it yourself.

    If you decide to rewrite something recursive yourself, please do not hesitate to show your code if you need any assistance.

    Update: ooops, as I was just going to post this, I was rereading your original message and it appears that I got carried away by your mention of the recursive formula and by Keath's comment on the fact that it is not recursive. It seems that, contrary to my assumption above, your professor did not ask for a recursive program, so that my comments above are not that useful. Well, I post them nonetheless, it might still be useful to someone or to you at a later point.
  8. #5
  9. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Oct 2013
    Posts
    37
    Rep Power
    2
    All help is appreciated, brother. And it's great for you to even post your input. Thanks

    Now whether my program is recursive or not, I think that it is, but I'm not sure if recursion is defined differently in computer science circles. This is my completed program, and this program can give you the pascal entry for any row and column. It starts at count 1, calculates a product, than multiplies it by the product of the count above it. It recursively multiples products until I get to the jth column. I've checked it and it seems to work for all values I have the pascal entry for.

    #!/usr/bin/env perl


    clear;

    print "Enter the row of your pascal Triangle\n";
    my $i = <STDIN>;

    print "Now enter the column of the pascal triangle\n";

    my $j = <STDIN>;

    my $count = 1;

    my $p = ($i - $count + 1)/($count);


    if ($j > $i ) {
    print "Your column length must not be larger than your row length";

    }else {
    until ($count == $j ) {
    $p *= ($i - $count )/($count +1);
    $count++;
    }
    print "\n$p\n";
    }
  10. #6
  11. No Profile Picture
    Contributing User
    Devshed Novice (500 - 999 posts)

    Join Date
    Jun 2012
    Location
    Paris area, France
    Posts
    842
    Rep Power
    496
    Great! I am happy that you succeeded.

    Having said that, please note that your program is definitely not recursive. And I can tell you that recursion is a sufficiently fundamental concept in CS (and in mathematics) so that there cannot be two different interpretations about that: even if your program is implementing a recursive mathematic definition of the Pascal triangle, your program is iterative (i.e. using a loop), but not recursive (i.e. using a function that calls itself).

    If you wanna see a recursive program, look at the one I gave you in the other post: you will see that, in the last line of the Pascal function, the function calls again itself (actually twice, in that case). Or consider the following simpler example, a recursive implementation of the factorial function (the archetypal example of recursion):

    Perl Code:
    sub fact {
         my $val = shift;
         return undef if $val < 0 or $val != int ($val); # fact defined only for positive integers
         return 1 if $val == 1 or $val == 0:    # 1! = 1 and 0! = 1
         return $val * fact ($val -1);   # n! = n * (n-1)!
    }


    If you call the fact function above with the parameter 3 (to calculate 3!), the function will go to line 5, and figure out that 3! = 3 * 2!, and it will call itself with the parameter 2 to calculate 2!. Called with value 2, the function will again go to line 5 and see that 2! = 2 * 1! and will call itself again with the parameter 1. Called with value 1, the function will stop at line 4, figure out that 1! = 1 and return 1 to the calling process. The previous function call will now be able to complete and figure out that 2! is 2 * 1 = 2 and return 2 to its caller. The first function call will now complete and figure out that 3! = 3 * 2 = 6, which is indeed the value of 3! This is what recursion is about.

    I took the time to explain it because, if you are studying CS, you will necessarily encounter recursion pretty soon. That gives you a first idea of what it is and how it works. It is actually very simple once you've grasped it, but often fairly difficult to understand the first time you see it. As an old CS saying goes, "to understand recursion, you first have to... understand recursion."

IMN logo majestic logo threadwatch logo seochat tools logo