Question on Recursion

prasadbabu has asked for the wisdom of the Perl Monks concerning the following question:

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 )
[download]

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

Thanks in advance

Prasad

updated: added the line, 'Because of that I am not getting final output '1818 == 9' in the main program.'

Comment on Question on Recursion Select or Download Code

Replies are listed 'Best First'.
Re: Question on Recursion by ikegami (Patriarch) on Jan 09, 2009 at 11:06 UTC
You're ignoring the result of the recursive call. `&spl($total) if ($len != 1);` [download] should be `$total = &spl($total) if ($len != 1);` [download] 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; } }` [download] 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; }` [download] or even `use List::Util qw( sum ); sub spl { my ($n) = @_; while (length($n) > 1) { $n = sum split '', $n; } return $n; }` [download] Update: Added last snippet.	[reply] [d/l] [select]
Re^2: Question on Recursion by AnomalousMonk (Archbishop) on Jan 09, 2009 at 19:23 UTC
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` [download]	[reply] [d/l]
Re: Question on Recursion by moritz (Cardinal) on Jan 09, 2009 at 11:07 UTC
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) } }` [download]	[reply] [d/l]
Re: Question on Recursion by JavaFan (Canon) on Jan 09, 2009 at 11:52 UTC
Now that you have found the recursion problem, I'd write it without recursion. Or looping. `print "$num == 9\n" unless $num % 9;` [download] will do as well.	[reply] [d/l]
Re^2: Question on Recursion by roboticus (Chancellor) on Jan 09, 2009 at 13:23 UTC
JavaFan: Not quite ... it'll only print the 9s! I'd suggest: `print "num=$num, result=", ($num ? substr("912345678", $num%9, 1) : 0) +, "\n";` [download] ...roboticus	[reply] [d/l]
Re^3: Question on Recursion by JavaFan (Canon) on Jan 09, 2009 at 13:26 UTC
Well, considering the OP has: `print "$num == 9\n" if ($total1 == 9);` [download] only printing the 9s was done on purpose, as that's what the OP is doing.	[reply] [d/l]
Re^4: Question on Recursion by roboticus (Chancellor) on Jan 09, 2009 at 13:29 UTC


"be consistent"
	PerlMonks