Can someone explain the logic of the recursion code and when it's best to use?

Question

I'm learning perl and I want to understand the logic better so I can improve in programming. I was wondering if anyone could explain it part by part. I think I have a good grasp of what's happening instead of this line $num = $val * fact($val-1); ?

#!/usr/bin/perl
use warnings;
use strict;

print "Enter in a number\n";
my $input = <>;

my $num = fact($input);
print "The factorial of $input is $num\n";

sub fact {
    my $val = $_[0];
    if ( $val > 1 ) {
        $num = $val * fact( $val - 1 );
    }
    else {
        $num = 1;
    }
}
exit;

score 3 · Accepted Answer · edited May 23 '17 at 10:26

The first line is the shebang, which specifies which version of Perl to use.

#!/usr/bin/perl

The next two lines will help you catch mistakes in your program and make sure you are coding properly. See Why use strict and warnings?

use warnings;
use strict;

print will print the message in quotes.

print "Enter in a number\n";

The diamond operator, <>, used in this context, is the same as calling readline. It will read the input from STDIN.

  my $input=<>;

The next line is calling the subroutine fact with $input as an argument.

my $num= fact($input);

Printing the result. $input and $num will be interpolated because you are using double quotes.

  print "The factorial of $input is $num\n";

Finally, the part you are most interested in.

sub fact{
 my $val = $_[0];
     if ($val > 1) {
        $num = $val * fact($val-1);
     } else {
        $num = 1;
     }
   }

The first line of this subroutine my $val = $_[0];, is setting $val equal to the value you call it with. The first time through, you call is with $input, so $val will be set to that value.

Next, we have this if else statement. Suppose you enter 5 on the command line, so $input was 5. In that case, it is greater than 1. It will execute the statement $num = $val * fact($val-1);. Seeing as the value of $val is 5, it would be the same as calling $num = 5 * fact(4);.

If we were going to continue looking at the what code is executing, you'll see that now we are calling fact(4);. Since 4 > 1 it will pass the if statement again, and then call fact(3).

Each time we are multiplying the number by that number minus one, such as $val = 5 * 4 * 3 * 2 * 1.

From perlsub

If no return is found and if the last statement is an expression, its value is returned. If the last statement is a loop control structure like a foreach or a while , the returned value is unspecified. The empty sub returns the empty list.

So this is why we don't have to return $num at the end of your fact subroutine, but it may be useful to add to increase readability.

Just to break down what this is doing.

$num = 5 * fact(4);

fact(4) is equivalent to 4 * fact(3).

$num = 5 * (4 * fact(3));

fact(3) is equivalent to 3 * fact(2).

$num = 5 * (4 * (3 * fact(2)));

fact(2) is equivalent to 2 * fact(1).

$num = 5 * (4 * (3 * (2 * fact(1)));

fact(1) is equivalent to 1.

$num = 5 * (4 * (3 * (2 * 1));

Search recursion on Google for another example (did you mean recursion?).

score 2 · Answer 2 · answered Jul 09 '14 at 13:14

As a wise man once said: "To understand recursion, you must first understand recursion."

Anyway - there are a bunch of algorithms that can work recursively. Factorial is one.

A factorial of 5! = 5*4*3*2*1. This makes it quite a good case for recursion, because you could also say it's 5 * 4!. This is what the code is doing. When you supply a number to the subroutine 'fact' it calculates the factorial of one number lower, then multiplies by the original number. Except when it gets a value of 1 or less.

So give your fact "3" to start off. (same applies to bigger numbers, but the example is longer!)

It sets val to '3'.
Then, because '3 > 1' it goes and gets 'fact(2)'.
- which because 2 > 1, goes and runs 'fact(1)'.
  - which because it isn't >1, returns '1'.
- which is returned to the 'fact(2)' sub, multiple by '2' (giving 2) and returned as a result
to the 'fact(3) sub, which multiplies the returned result by 3, to give 6.

Personally I find recursion is a good way to confuse anyone who's reading your code. It's suitable for problems that are implicitly recursive - such as factorials, fibonnaci sequences and directory traversals - and generally should be avoided otherwise.

score 1 · Answer 3 · answered Jul 09 '14 at 17:41

The reason you're having trouble learning from that code is because it's poorly designed:

The subroutine needlessly uses a lexical variable ($num) from outside the subroutine. Don't do this!
The subroutine relies on implied return values instead of specifying return explicitly.

Fixing these issues clarifies the functionality a lot:

sub fact {
    my $val = $_[0];
    if ( $val > 1 ) {
        return $val * fact( $val - 1 );
    }
    else {
        return 1;
    }
}

And then using a ternary to reduce more:

sub fact {
    my $val = shift;
    return $val > 1 ? $val * fact( $val - 1 ) : 1;
}

As for when recursion is good to use? The answer is when you need it.

The factorial is an obvious example of where recursion could be used, but it's better to avoid using it when one has a choice. This is for both readability and functional reasons:

sub fact {
    my $val = shift;

    my $fact = 1;
    while ($val > 1) {
        $fact *= $val--;
    }

    return $fact;
}

Can someone explain the logic of the recursion code and when it's best to use?

3 Answers3