Subroutine recursion in Perl

Question

EDIT: I'm glad no one has spent any time pointing out that the actual text in line 6 and 7 has a different number than the input for their respective function calls. Eventually I'll be doing it for those two numbers (724 and 27), but for the sake of troubleshooting, I picked numbers with much smaller sequences. So, if anyone was wondering, that's why...

So, I've been learning Perl, and am relatively new to programming in general. My supervisor has a set of exercises for me to go through. The current one deals with Hailstone sequences, and she wants me to write a subroutine that prints the sequence for a given number.

The problem I'm running into is that, no matter what I've tried, if I call the function more than once, it will produce the sequence for the first number I call the function with, but the second time I call the function, it produces the sequence of the first call followed by the sequence of the second. So, this code:

#!usr/bin/perl

use strict;
use warnings; 

print "\nThe hailstone sequence for 724 is:\n" . &hail(8) . "\n\n";
print "The hailstone sequence for 27 is:\n" . &hail(16) . "\n\n";

my $n;
my @seq;
sub hail {
    no warnings 'recursion';
    $n = $_[0];
    if ($n > 1) {
            push @seq, $n;
            if ($n % 2 == 0) {
                    $n = $n/2;
            } else {
                    $n = (3 * $n) + 1;
            }
            &hail($n);
    } else {
            push @seq, $n;
    }
    return "@seq";
}

produces:

The hailstone sequence for 724 is:
8 4 2 1

The hailstone sequence for 27 is:
8 4 2 1 16 8 4 2 1

I understand that this is most likely due to the fact that @seq doesn't get cleared out after each time the subroutine runs, but I've tried as many different ways as I can think of to clear it out so that each time I call the subroutine, it displays the sequence for -only- that number but they all either result in what I show here, or in showing nothing. How do I go about clearing the array each time?

Thanks very much.

Blackstock

Not related to your main point, but don't use & to call subroutines in Perl. That's an old and obsolete practice (except in certain advanced and obscure instances you don't need to worry about yet). Just use hail(8). – Crusade

Another point not related to your question: why return an array as a string? return "@seq" ? – Rustice

@Arkadiy Because I need to reread ch. 3 of Learning Perl. I just know that @seq and "@seq" produce two different things, and "@seq" was working for what I was trying at the time. There's another part of the exercise where I do need the number of elements in a given sequence, and return @seq is working beautifully for that, now I'm just working back from that to actually display the sequence. – Blackstock

Answer 1

You don't need recursion here. In my Fibonacci example in Mastering Perl, I show that it's easier to do it with iteration where you manage the queue yourself rather than using the call stack to do it.

Here's a general iterative solution that uses an array to keep track of the work left to do:

use strict;
use warnings;
use v5.10;

say "The hailstone sequence for 724 is:\n\t" .
    join " ", hail(8);
say "The hailstone sequence for 27 is:\n\t"  .
    join " ", hail(16);


sub hail {
    my @queue    = ( $_[0] );
    my @sequence = ();

    while( my $next = shift @queue ) {
        if( $next > 1 ) {
            push @queue, do {
                if( $next % 2 == 0 ) { $next / 2 }
                else                 { 3*$next + 1 }
                };
            }

        push @sequence, $next;
        }

    @sequence;
    }

From there, I could add caching and other things so I can reuse sequences I've already generated (which works even without showing off some exciting new Perl features such as subroutine signatures and postfix dereferencing that I find quite fun):

use strict;
use warnings;
use v5.22;

use feature qw(signatures postderef);
no warnings qw(experimental::signatures experimental::postderef);

say "The hailstone sequence for 724 is:\n\t" .
    join " ", hail(8)->@*;
say "The hailstone sequence for 27 is:\n\t"  .
    join " ", hail(16)->@*;


sub hail ( $n ) {
    my @queue    = ( $_[0] );
    state $sequence = { 1 => [ 1 ] };

    return $sequence->{$n} if exists $sequence->{$n};

    my @sequence = ();

    while( my $next = shift @queue ) {
        say "Processing $next";  # to watch what happens
        if( exists $sequence->{$next} ) {
            push @sequence, $sequence->{$next}->@*;
            next;
            }

        push @queue, do {
            if( $next % 2 == 0 ) { $next / 2 }
            else                 { 3*$next + 1 }
            };

        push @sequence, $next;
        }

    $sequence->{$n} = \@sequence;
    }

I threw a say in there to show what I process. You can see that with 16, it doesn't have to go past 8 because it already knows that answer:

Processing 8
Processing 4
Processing 2
Processing 1
The hailstone sequence for 724 is:
    8 4 2 1
Processing 16
Processing 8
The hailstone sequence for 27 is:
    16 8 4 2 1

I was curious which numbers might cause a problem, so I slightly modified your example to return a list so I could easily count the number of elements. Several numbers produced sequences with over 100 numbers:

use strict;
use warnings;
use v5.10;

foreach my $n ( 0 .. 100 ) {
    hail( $n, \my @seq );
    say "$n [" . @seq . "] @seq";
    }

sub hail {
    my $n = $_[0];
    my $s = $_[1];

    if ($n > 1) {
            push @$s, $n;
            if ($n % 2 == 0) {
                    $n = $n/2;
            } else {
                    $n = (3 * $n) + 1;
            }
            hail($n, $s);
    } else {
            push @$s, $n;
    }
}

The output, without the deep recursion warnings (which should be the hint not to do it that way ;):

0 [1] 0
1 [1] 1
2 [2] 2 1
3 [8] 3 10 5 16 8 4 2 1
4 [3] 4 2 1
5 [6] 5 16 8 4 2 1
6 [9] 6 3 10 5 16 8 4 2 1
7 [17] 7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
8 [4] 8 4 2 1
9 [20] 9 28 14 7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
10 [7] 10 5 16 8 4 2 1
11 [15] 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
12 [10] 12 6 3 10 5 16 8 4 2 1
13 [10] 13 40 20 10 5 16 8 4 2 1
14 [18] 14 7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
15 [18] 15 46 23 70 35 106 53 160 80 40 20 10 5 16 8 4 2 1
16 [5] 16 8 4 2 1
17 [13] 17 52 26 13 40 20 10 5 16 8 4 2 1
18 [21] 18 9 28 14 7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
19 [21] 19 58 29 88 44 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
20 [8] 20 10 5 16 8 4 2 1
21 [8] 21 64 32 16 8 4 2 1
22 [16] 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
23 [16] 23 70 35 106 53 160 80 40 20 10 5 16 8 4 2 1
24 [11] 24 12 6 3 10 5 16 8 4 2 1
25 [24] 25 76 38 19 58 29 88 44 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
26 [11] 26 13 40 20 10 5 16 8 4 2 1
27 [112] 27 82 41 124 62 31 94 47 142 71 214 107 322 161 484 242 121 364 182 91 274 137 412 206 103 310 155 466 233 700 350 175 526 263 790 395 1186 593 1780 890 445 1336 668 334 167 502 251 754 377 1132 566 283 850 425 1276 638 319 958 479 1438 719 2158 1079 3238 1619 4858 2429 7288 3644 1822 911 2734 1367 4102 2051 6154 3077 9232 4616 2308 1154 577 1732 866 433 1300 650 325 976 488 244 122 61 184 92 46 23 70 35 106 53 160 80 40 20 10 5 16 8 4 2 1
28 [19] 28 14 7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
29 [19] 29 88 44 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
30 [19] 30 15 46 23 70 35 106 53 160 80 40 20 10 5 16 8 4 2 1
31 [107] 31 94 47 142 71 214 107 322 161 484 242 121 364 182 91 274 137 412 206 103 310 155 466 233 700 350 175 526 263 790 395 1186 593 1780 890 445 1336 668 334 167 502 251 754 377 1132 566 283 850 425 1276 638 319 958 479 1438 719 2158 1079 3238 1619 4858 2429 7288 3644 1822 911 2734 1367 4102 2051 6154 3077 9232 4616 2308 1154 577 1732 866 433 1300 650 325 976 488 244 122 61 184 92 46 23 70 35 106 53 160 80 40 20 10 5 16 8 4 2 1
32 [6] 32 16 8 4 2 1
33 [27] 33 100 50 25 76 38 19 58 29 88 44 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
34 [14] 34 17 52 26 13 40 20 10 5 16 8 4 2 1
35 [14] 35 106 53 160 80 40 20 10 5 16 8 4 2 1
36 [22] 36 18 9 28 14 7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
37 [22] 37 112 56 28 14 7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
38 [22] 38 19 58 29 88 44 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
39 [35] 39 118 59 178 89 268 134 67 202 101 304 152 76 38 19 58 29 88 44 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
40 [9] 40 20 10 5 16 8 4 2 1
41 [110] 41 124 62 31 94 47 142 71 214 107 322 161 484 242 121 364 182 91 274 137 412 206 103 310 155 466 233 700 350 175 526 263 790 395 1186 593 1780 890 445 1336 668 334 167 502 251 754 377 1132 566 283 850 425 1276 638 319 958 479 1438 719 2158 1079 3238 1619 4858 2429 7288 3644 1822 911 2734 1367 4102 2051 6154 3077 9232 4616 2308 1154 577 1732 866 433 1300 650 325 976 488 244 122 61 184 92 46 23 70 35 106 53 160 80 40 20 10 5 16 8 4 2 1
42 [9] 42 21 64 32 16 8 4 2 1
43 [30] 43 130 65 196 98 49 148 74 37 112 56 28 14 7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
44 [17] 44 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
45 [17] 45 136 68 34 17 52 26 13 40 20 10 5 16 8 4 2 1
46 [17] 46 23 70 35 106 53 160 80 40 20 10 5 16 8 4 2 1
47 [105] 47 142 71 214 107 322 161 484 242 121 364 182 91 274 137 412 206 103 310 155 466 233 700 350 175 526 263 790 395 1186 593 1780 890 445 1336 668 334 167 502 251 754 377 1132 566 283 850 425 1276 638 319 958 479 1438 719 2158 1079 3238 1619 4858 2429 7288 3644 1822 911 2734 1367 4102 2051 6154 3077 9232 4616 2308 1154 577 1732 866 433 1300 650 325 976 488 244 122 61 184 92 46 23 70 35 106 53 160 80 40 20 10 5 16 8 4 2 1
48 [12] 48 24 12 6 3 10 5 16 8 4 2 1
49 [25] 49 148 74 37 112 56 28 14 7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
50 [25] 50 25 76 38 19 58 29 88 44 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
51 [25] 51 154 77 232 116 58 29 88 44 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
52 [12] 52 26 13 40 20 10 5 16 8 4 2 1
53 [12] 53 160 80 40 20 10 5 16 8 4 2 1
54 [113] 54 27 82 41 124 62 31 94 47 142 71 214 107 322 161 484 242 121 364 182 91 274 137 412 206 103 310 155 466 233 700 350 175 526 263 790 395 1186 593 1780 890 445 1336 668 334 167 502 251 754 377 1132 566 283 850 425 1276 638 319 958 479 1438 719 2158 1079 3238 1619 4858 2429 7288 3644 1822 911 2734 1367 4102 2051 6154 3077 9232 4616 2308 1154 577 1732 866 433 1300 650 325 976 488 244 122 61 184 92 46 23 70 35 106 53 160 80 40 20 10 5 16 8 4 2 1
55 [113] 55 166 83 250 125 376 188 94 47 142 71 214 107 322 161 484 242 121 364 182 91 274 137 412 206 103 310 155 466 233 700 350 175 526 263 790 395 1186 593 1780 890 445 1336 668 334 167 502 251 754 377 1132 566 283 850 425 1276 638 319 958 479 1438 719 2158 1079 3238 1619 4858 2429 7288 3644 1822 911 2734 1367 4102 2051 6154 3077 9232 4616 2308 1154 577 1732 866 433 1300 650 325 976 488 244 122 61 184 92 46 23 70 35 106 53 160 80 40 20 10 5 16 8 4 2 1
56 [20] 56 28 14 7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
57 [33] 57 172 86 43 130 65 196 98 49 148 74 37 112 56 28 14 7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
58 [20] 58 29 88 44 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
59 [33] 59 178 89 268 134 67 202 101 304 152 76 38 19 58 29 88 44 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
60 [20] 60 30 15 46 23 70 35 106 53 160 80 40 20 10 5 16 8 4 2 1
61 [20] 61 184 92 46 23 70 35 106 53 160 80 40 20 10 5 16 8 4 2 1
62 [108] 62 31 94 47 142 71 214 107 322 161 484 242 121 364 182 91 274 137 412 206 103 310 155 466 233 700 350 175 526 263 790 395 1186 593 1780 890 445 1336 668 334 167 502 251 754 377 1132 566 283 850 425 1276 638 319 958 479 1438 719 2158 1079 3238 1619 4858 2429 7288 3644 1822 911 2734 1367 4102 2051 6154 3077 9232 4616 2308 1154 577 1732 866 433 1300 650 325 976 488 244 122 61 184 92 46 23 70 35 106 53 160 80 40 20 10 5 16 8 4 2 1
63 [108] 63 190 95 286 143 430 215 646 323 970 485 1456 728 364 182 91 274 137 412 206 103 310 155 466 233 700 350 175 526 263 790 395 1186 593 1780 890 445 1336 668 334 167 502 251 754 377 1132 566 283 850 425 1276 638 319 958 479 1438 719 2158 1079 3238 1619 4858 2429 7288 3644 1822 911 2734 1367 4102 2051 6154 3077 9232 4616 2308 1154 577 1732 866 433 1300 650 325 976 488 244 122 61 184 92 46 23 70 35 106 53 160 80 40 20 10 5 16 8 4 2 1
64 [7] 64 32 16 8 4 2 1
65 [28] 65 196 98 49 148 74 37 112 56 28 14 7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
66 [28] 66 33 100 50 25 76 38 19 58 29 88 44 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
67 [28] 67 202 101 304 152 76 38 19 58 29 88 44 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
68 [15] 68 34 17 52 26 13 40 20 10 5 16 8 4 2 1
69 [15] 69 208 104 52 26 13 40 20 10 5 16 8 4 2 1
70 [15] 70 35 106 53 160 80 40 20 10 5 16 8 4 2 1
71 [103] 71 214 107 322 161 484 242 121 364 182 91 274 137 412 206 103 310 155 466 233 700 350 175 526 263 790 395 1186 593 1780 890 445 1336 668 334 167 502 251 754 377 1132 566 283 850 425 1276 638 319 958 479 1438 719 2158 1079 3238 1619 4858 2429 7288 3644 1822 911 2734 1367 4102 2051 6154 3077 9232 4616 2308 1154 577 1732 866 433 1300 650 325 976 488 244 122 61 184 92 46 23 70 35 106 53 160 80 40 20 10 5 16 8 4 2 1
72 [23] 72 36 18 9 28 14 7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
73 [116] 73 220 110 55 166 83 250 125 376 188 94 47 142 71 214 107 322 161 484 242 121 364 182 91 274 137 412 206 103 310 155 466 233 700 350 175 526 263 790 395 1186 593 1780 890 445 1336 668 334 167 502 251 754 377 1132 566 283 850 425 1276 638 319 958 479 1438 719 2158 1079 3238 1619 4858 2429 7288 3644 1822 911 2734 1367 4102 2051 6154 3077 9232 4616 2308 1154 577 1732 866 433 1300 650 325 976 488 244 122 61 184 92 46 23 70 35 106 53 160 80 40 20 10 5 16 8 4 2 1
74 [23] 74 37 112 56 28 14 7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
75 [15] 75 226 113 340 170 85 256 128 64 32 16 8 4 2 1
76 [23] 76 38 19 58 29 88 44 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
77 [23] 77 232 116 58 29 88 44 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
78 [36] 78 39 118 59 178 89 268 134 67 202 101 304 152 76 38 19 58 29 88 44 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
79 [36] 79 238 119 358 179 538 269 808 404 202 101 304 152 76 38 19 58 29 88 44 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
80 [10] 80 40 20 10 5 16 8 4 2 1
81 [23] 81 244 122 61 184 92 46 23 70 35 106 53 160 80 40 20 10 5 16 8 4 2 1
82 [111] 82 41 124 62 31 94 47 142 71 214 107 322 161 484 242 121 364 182 91 274 137 412 206 103 310 155 466 233 700 350 175 526 263 790 395 1186 593 1780 890 445 1336 668 334 167 502 251 754 377 1132 566 283 850 425 1276 638 319 958 479 1438 719 2158 1079 3238 1619 4858 2429 7288 3644 1822 911 2734 1367 4102 2051 6154 3077 9232 4616 2308 1154 577 1732 866 433 1300 650 325 976 488 244 122 61 184 92 46 23 70 35 106 53 160 80 40 20 10 5 16 8 4 2 1
83 [111] 83 250 125 376 188 94 47 142 71 214 107 322 161 484 242 121 364 182 91 274 137 412 206 103 310 155 466 233 700 350 175 526 263 790 395 1186 593 1780 890 445 1336 668 334 167 502 251 754 377 1132 566 283 850 425 1276 638 319 958 479 1438 719 2158 1079 3238 1619 4858 2429 7288 3644 1822 911 2734 1367 4102 2051 6154 3077 9232 4616 2308 1154 577 1732 866 433 1300 650 325 976 488 244 122 61 184 92 46 23 70 35 106 53 160 80 40 20 10 5 16 8 4 2 1
84 [10] 84 42 21 64 32 16 8 4 2 1
85 [10] 85 256 128 64 32 16 8 4 2 1
86 [31] 86 43 130 65 196 98 49 148 74 37 112 56 28 14 7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
87 [31] 87 262 131 394 197 592 296 148 74 37 112 56 28 14 7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
88 [18] 88 44 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
89 [31] 89 268 134 67 202 101 304 152 76 38 19 58 29 88 44 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
90 [18] 90 45 136 68 34 17 52 26 13 40 20 10 5 16 8 4 2 1
91 [93] 91 274 137 412 206 103 310 155 466 233 700 350 175 526 263 790 395 1186 593 1780 890 445 1336 668 334 167 502 251 754 377 1132 566 283 850 425 1276 638 319 958 479 1438 719 2158 1079 3238 1619 4858 2429 7288 3644 1822 911 2734 1367 4102 2051 6154 3077 9232 4616 2308 1154 577 1732 866 433 1300 650 325 976 488 244 122 61 184 92 46 23 70 35 106 53 160 80 40 20 10 5 16 8 4 2 1
92 [18] 92 46 23 70 35 106 53 160 80 40 20 10 5 16 8 4 2 1
93 [18] 93 280 140 70 35 106 53 160 80 40 20 10 5 16 8 4 2 1
94 [106] 94 47 142 71 214 107 322 161 484 242 121 364 182 91 274 137 412 206 103 310 155 466 233 700 350 175 526 263 790 395 1186 593 1780 890 445 1336 668 334 167 502 251 754 377 1132 566 283 850 425 1276 638 319 958 479 1438 719 2158 1079 3238 1619 4858 2429 7288 3644 1822 911 2734 1367 4102 2051 6154 3077 9232 4616 2308 1154 577 1732 866 433 1300 650 325 976 488 244 122 61 184 92 46 23 70 35 106 53 160 80 40 20 10 5 16 8 4 2 1
95 [106] 95 286 143 430 215 646 323 970 485 1456 728 364 182 91 274 137 412 206 103 310 155 466 233 700 350 175 526 263 790 395 1186 593 1780 890 445 1336 668 334 167 502 251 754 377 1132 566 283 850 425 1276 638 319 958 479 1438 719 2158 1079 3238 1619 4858 2429 7288 3644 1822 911 2734 1367 4102 2051 6154 3077 9232 4616 2308 1154 577 1732 866 433 1300 650 325 976 488 244 122 61 184 92 46 23 70 35 106 53 160 80 40 20 10 5 16 8 4 2 1
96 [13] 96 48 24 12 6 3 10 5 16 8 4 2 1
97 [119] 97 292 146 73 220 110 55 166 83 250 125 376 188 94 47 142 71 214 107 322 161 484 242 121 364 182 91 274 137 412 206 103 310 155 466 233 700 350 175 526 263 790 395 1186 593 1780 890 445 1336 668 334 167 502 251 754 377 1132 566 283 850 425 1276 638 319 958 479 1438 719 2158 1079 3238 1619 4858 2429 7288 3644 1822 911 2734 1367 4102 2051 6154 3077 9232 4616 2308 1154 577 1732 866 433 1300 650 325 976 488 244 122 61 184 92 46 23 70 35 106 53 160 80 40 20 10 5 16 8 4 2 1
98 [26] 98 49 148 74 37 112 56 28 14 7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
99 [26] 99 298 149 448 224 112 56 28 14 7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1
100 [26] 100 50 25 76 38 19 58 29 88 44 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1

Cara

Problems with this post: 1) This post correct states that recursion is not needed, but doesn't mention why you'd want to avoid recursion. 2) The post expects the reader to know that "iterative" is commonly used to mean "non-recursive". 3) This post uses a very complicate means of removing recursion, but doesn't explain why. 4) This post provides a very complicated iterative solution when much simpler ones exist. 5) It also calls this iterative solution easier. 6) This posts requires a version of Perl the OP is unlikely to have. This is harmful, especially since the OP is still learning Perl. – Elfreda

I get it. You don't like me and need to rationalize it. Just ignore me and move on. – Cara

@Elfreda I take things with a grain of salt, being not only new to Perl, but scripting/computing in general. I actually came in assuming people would give me answers beyond what I really understand doing, so things that you would consider "harmful" don't bother me. briandfoy, my supervisor suggested using recursion. What I was working on at first didn't have it, but I was far enough from a solution anyway that I went ahead and tried doing as she suggested. I very much appreciate your feedback. – Blackstock

@frankenstein724, You're not the only reader, and even if you were, there's no reason to provide code that won't run when it's just as simple to provide code that does (meaning use @{ $sequence->{$next} } instead of $sequence->{$next}->@*). – Elfreda

Answer 2

Should you want a true function — one that doesn't have any side-effects, and thus none of the problems you are having — it would look as follows:

sub hail {
    no warnings qw( recursion );
    my ($n) = @_;
    if ($n > 1) {
        if ($n % 2 == 0) {
            return $n, hail($n/2);
        } else {
            return $n, hail(3*$n + 1);
        }
    } else {
        return $n;
    }
}

Note that recursion is totally unneeded here, greatly slowing down your program and increasing its memory footprint. The following is such an iterative solution:

sub hail {
    my ($n) = @_;
    my @rv;
    while (1) {
        push @rv, $n;
        last if $n <= 1;

        if ($n % 2 == 0) {
            $n = $n/2;
        } else {
            $n = 3*$n + 1;
        }
    }

    return @rv;
}

---

A question about the above code was asked in the comments. The following is the answer:

last jumps to the statement after the loop.

Another programmer might have written the following:

push @rv, $n;
while ($n > 1) {
   ...;
   push @rv, $n;
}

But that contains duplicated code. Ideally, one seeks to avoid duplicated code. But since

while (EXPR) { STATEMENTS }

can be rewritten as

while (1) { last if !EXPR; STATEMENTS }

and since

push @rv, $n;
while ($n > 1) {
   ...;
   push @rv, $n;
}

can be rewritten as

push @rv, $n;
while (1) {
   last if $n <= 1;
   ...;
   push @rv, $n;
}

we can remove the duplicated code as follows:

while (1) {
   push @rv, $n;
   last if $n <= 1;
   ...;
}

Elfreda

Comma operator in list context with list flattening! All Hail Perl! – Rustice

The second sub should be last if $n <2 . – Ethelstan

@JRFerguson, Thanks, fixed. I didn't test the code because I wrote it on my phone. – Elfreda

Is while (1) more or less "while true", and once you get to the last there is no longer anything to be true, thus the loop stops? That might be horribly worded on my part, but if that's not more or less the idea, I'd like a little more explanation on while (1). – Blackstock

I've responded in my answer. – Elfreda

Answer 3

Not sure about perl, but in other languages I'd do

sub hail {
    my @seq;
    return hailRecursive(\@seq, $_[0])
}

And then implement hailRecursive in terms of array ref and $n

Rustice

Simpler: sub hail { hail_recursive([], @_) } – Elfreda

While the post is light on details, this is a very good approach as it makes the hailRecursive tail-recursive. Some languages can optimize this type of recursion away automatically in such cases (to speed things up and save memory), but unfortunately not Perl. OTOH, it makes it easy to manually remove the recursion manually. – Elfreda

Answer 4

So, the full assignment was to print the sequence for any number < 100000 of my choosing, print the sequence of 27, and then find the number < 100000 with the longest sequence, and print the number of elements in the sequence (but not the sequence itself) I greatly appreciate the help everyone has provided about making a more effective subroutine, and I really will go through the different suggestions to learn the different tips and tricks from each one. I didn't modify my main subroutine code too much to keep it more in my (current) style for the sake of the exercise. (My supervisor won't care that I got help, but it still feels...-something-...to just copy somebody else's code without also knowing I could figure it out with my own hair-brained ideas, along with -her- suggestion to use a recursive subroutine, as well).

I took one person's advice to not return the array as a string, which helped with the part of the exercise I didn't originally mention, but then I had to rework how I printed the actual sequences which seemed easy enough. Beyond learning more effective subroutines, my main concern is still with clearing the array. Someone suggested just putting @seq = () after each instance, and that works. What I want to know is why what I actually have running in the code (the lines with ##### -after- the code) works to clear the array each time, but why it doesn't work to simply clear out the array after I return it in the subroutine, like I have with the commented out line. That still aggregates the sequence each time the subroutine is called.

#!usr/bin/perl

use strict;
use warnings;

my $num_win = 0;
my $elem_win = 0;
my @seq;
my $elements;

print "\nThe hailstone sequence for 724 is:\n";
&sequence(&hail(724));
@seq = ();      #####

print "\n\nThe hailstone sequence for 27 is:\n";
&sequence(&hail(27));
@seq = ();      #####

for (my $i=1; $i<100000; $i++) {
    $elements = &hail($i);
    if ($elements > $elem_win) {
            $elem_win = $elements;
            $num_win = $i;
    }
    @seq = ();      #####
}

print "\n\nThe number with the largest sequence is: $num_win\n";
print "The number of elements in $num_win is: $elem_win\n\n";

my $n;
sub hail {
    no warnings 'recursion';
    $n = $_[0];
    if ($n > 1) {
            push @seq, $n;
            if ($n % 2 == 0) {
                    $n = $n/2;
            } else {
                    $n = (3 * $n) + 1;
            }
            &hail($n);
    } else {
            push @seq, $n;
    }
    return @seq;
#####   @seq = ();
}

sub sequence {
    my @hail_seq = @_;
    foreach (@hail_seq) {
            my $number = $_;
            print "$number, ";
    }
}

with the results:

The hailstone sequence for 724 is:
724, 362, 181, 544, 272, 136, 68, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 

The hailstone sequence for 27 is:
27, 82, 41, 124, 62, 31, 94, 47, 142, 71, 214, 107, 322, 161, 484, 242, 121, 364, 182, 91, 274, 137, 412, 206, 103, 310, 155, 466, 233, 700, 350, 175, 526, 263, 790, 395, 1186, 593, 1780, 890, 445, 1336, 668, 334, 167, 502, 251, 754, 377, 1132, 566, 283, 850, 425, 1276, 638, 319, 958, 479, 1438, 719, 2158, 1079, 3238, 1619, 4858, 2429, 7288, 3644, 1822, 911, 2734, 1367, 4102, 2051, 6154, 3077, 9232, 4616, 2308, 1154, 577, 1732, 866, 433, 1300, 650, 325, 976, 488, 244, 122, 61, 184, 92, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1, 

The number with the largest sequence is: 77031
The number of elements in 77031 is: 351

Blackstock

Answer 5

Change your 2nd else block to this and remove the return statement after that block.

else {
    push @seq, $n;
    my $seq = "@seq";
    undef @seq;
    return $seq;
}

Sula

Could you do that while still returning an array useful in list context, rather than a string? Please? – Rustice

Answer 6

You just need to initialize the array @seq before calling the hail subroutine a second time. Try this ...

my @seq;
print "\nThe hailstone sequence for 724 is:\n" . &hail(8) . "\n\n";
@seq = ();
print "The hailstone sequence for 27 is:\n" . &hail(16) . "\n\n";

my $n;

Giralda

Broken encapsulation! – Rustice

Answer 7

Similar to what others have posted.

sub hailstone {
    my $n = shift;
    return if $n == 1;
    if ( $n % 2 == 0 ){
        $n = $n / 2;
    } else {
        $n = ( $n * 3 ) + 1;
    }
    return $n."\n",hailstone($n)
}

Upon calling the subroutine:

say hailstone(5);
16
8
4
2
1

Shively