Question on Recursion

[prasadbabu]

Hi Monks,

Today I wrote a small script for my friend to check the sum of the digits recursively (till single digit of length), numbers range from 1500 to 2300. For example:

Number 1818
1818 = 1+8+1+8 = 36   step 1 (2 digits output)
36   = 3 + 6 = 9      step 2 (single digit output)
result: 9 (final count of the digits )

I wrote the below code and found the final total is printing continuously. I expected only 9 but it is printing both 9 and 18 continuously. I solved the issue later (case 2). But I want to know the reason why it is printing continuously 9 and 18. Because of that I am not getting final output '1818 == 9' in the main program.

I 'super searched' in perlmonks and found following links. subroutine recursion question,Recursion problem, Recursion. But I was not able to find correct answer. Even I googled but I didn't get correct answer. Even I flushed using $| but not able to get expected output. Where am I going wrong? Could someone explain where I am making mistake?

use strict;
use warnings;

my $total1;

for my $num (1818..1818){   
     
     my $total1 = &spl($num);             
     
     print "$num == 9\n" if ($total1 == 9);
     
}

################# not working as i expected ####### case 1

sub spl{
    
my ($num1) = @_;    

my $total = 0;

$total = $total + $_ for (split '', $num1);

print "total: $total\n";

my $len = length ($total);

print "length: $len\n";

&spl($total) if ($len != 1);

print "final: $total\n";

return $total;

}


########## working perfectly #########   case 2

#sub spl{
#    
#my ($num1) =@_;    
#
#my $total = 0;
#
#$total = $total + $_ for (split '', $num1);
#
#my $len = length ($total);
#
#return $total if ($len == 1);
#
#&spl($total) if ($len != 1);
#
#}


output:
-------
total: 18
length: 2
total: 9
length: 1
final: 9
final: 18

Expected output:
----------------
total: 18
length: 2
total: 9
length: 1
final: 9
1818 == 9

[ikegami]

You're ignoring the result of the recursive call.

&spl($total) if ($len != 1);

should be

$total = &spl($total) if ($len != 1);

Now, what we have here what is called tail-end recursion. The recursion is the last thing in the function. That means you can use a loop instead.

sub spl {
   my ($num1) = @_;    
   while (1) {
      my $total = 0;
      $total = $total + $_ for (split '', $num1);
      my $len = length ($total);
      if ($len == 1) {
         return $total;
      }
      $num1 = $total;
   }
}

After some cleaning up, we get:

sub spl {
   my ($n) = @_;    
   while (length($n) > 1) {
      my $total = 0;
      $total = $total + $_ for split '', $n;
      $n = $total;
   }
   return $n;
}

or even

use List::Util qw( sum );

sub spl {
   my ($n) = @_;    
   while (length($n) > 1) {
      $n = sum split '', $n;
   }
   return $n;
}

Update: Added last snippet.

[AnomalousMonk]

FWIW: Yet another snippet, slightly different approach:

>perl -wMstrict -le
"sub T {
  my $n = 0;
  $n += $_ for @_;
  return $n <= 9 ? $n : T(split '', $n);
  }
 printf qq{%5s -> %d \n}, $_, T($_) for @ARGV
"
1818  1819 1918  1500 5001 51  2300 0230 32
1 9 0 00 00000 10000 00001
 1818 -> 9
 1819 -> 1
 1918 -> 1
 1500 -> 6
 5001 -> 6
   51 -> 6
 2300 -> 5
 0230 -> 5
   32 -> 5
    1 -> 1
    9 -> 9
    0 -> 0
   00 -> 0
00000 -> 0
10000 -> 1
00001 -> 1

[moritz]

You get two lines with

final<c> because that print is unconditional. You could write it that 
+way instead:

<c>
sub spl {
   my ($num1) = @_;    
   my $total = 0;

   $total = $total + $_ for (split '', $num1);
   if (length($total) == 1) {
      print "Final: $total\n";
      return $total;
   } else {
      return spl($total)
  }
}

[JavaFan]

Now that you have found the recursion problem, I'd write it without recursion. Or looping.

print "$num == 9\n" unless $num % 9;

will do as well.

[roboticus]

JavaFan:

Not quite ... it'll only print the 9s! I'd suggest:

print "num=$num, result=", ($num ? substr("912345678", $num%9, 1) : 0)
+, "\n";

...roboticus

[JavaFan]

Well, considering the OP has:

print "$num == 9\n" if ($total1 == 9);

only printing the 9s was done on purpose, as that's what the OP is doing.