Several ways:

1. Simple closure:

   {
      my %state;
      sub recursive {
          my $arg = shift;
          ...
          if( ( $arg = $state{ $arg } ) == ... ) {
               return recursive( $arg );
          else {
               return 0
          }
      }
   }
   [download]

2. Closure via helper function:

   sub rec_helper {
       my %state;
       my $recursive;
       $recursive = sub {
           my( $arg ) = shift;
           ...
           if( ( $arg = $state{ $arg ) ) == ... ) {
                return $recursive->( $arg );
           }
           else {
                return 0;
           }
       };
   }
   [download]

3. State passed through args (often via helper function ):

   sub recursive {
       my( $state, $arg ) = @_;
       ...
       if( ( $arg = $state->{ $arg } ) == ... ) {
            return recursive( $state, $arg );
       }
       else {
            return 0;
       }
   }
   
   sub rec_helper{
       my $arg = shift;
       my %state;
       return recursive( \%state, $arg );
   }
   [download]

And many variations on those themes.

#2 leaks memory every time you call rec_helper. The sub you create references $recursive which references the sub, so you have a memory cycle. The simplest solution is to avoid using a lexical to hold the reference to the sub. It even simplifies the code a little.

sub rec_helper {
    my %state;
    local *recursive = sub {
        my( $arg ) = shift;
        ...
        if( ( $arg = $state{ $arg ) ) == ... ) {
             return recursive( $arg );
        }
        else {
             return 0;
        }
    };
}
[download]

{ my %memo;
  sub rec_func {
    my $key=key_from_input(@_);
    unless (exists $memo{$key}) {
       $memo{$key}=calculate(@_);
    } 
    return $memo{key};
  }
}
[download]

This should effectively cache complicated calculations based on the call-parameters...

(untested)

Of course you are free to decide what you are caching...

For that case, also see Memoize

I suppose he needs a more general flexibility to memoize based on more complicated input ("Level"?) Thats why I didn't mention Memoize

For those interested see Viterbi Algorithm and Algorithm-Viterbi

Cheers Rolf

Add strictures then turn your sketch into real code. At present there are too many places where it is not clear what you want to happen because of errors in your code (bare words 'begin' and 'end' and multiplications in void context for example). If the general help others have offered isn't enough to solve your problem then we need something that can actually be run.

It would be polite for you to make at least a minimal effort to understand the OP. For example, when the OP says

#maximum of below foreach#
            
 foreach my $yy ( keys %{$trans->{$state}} ) 

 {  $trans->{$state}->{$yy}  *  viterbi($yy, $r) ;  }
[download]

it's obvious he means max(map { ... } keys ...) We're humans here, not computers, so we should act like, and treat each other as, humans.

Of course, you're not obliged to make that effort. But if you don't want to, why waste everyone's time with an unhelpful comment?

In fact I spent on the order of half an hour playing with the OP's code, but I couldn't figure out what a useful starting condition might be. Revisiting the OP's node I've only just noticed the print "\n\n", viterbi(end, 3); at the end of the large code block. I guess I was misled by the comment 'this part is main part' following the first code fragment into thinking that was the driving code for what followed rather than the 'key part of the code' as, in hind sight, the OP presumably meant. On reflection it's not surprising that my static analysis of the code wasn't getting anywhere fast!

Bottom line? 'Don't attribute to malice what you can account for by stupidity!'

True laziness is hard work

It's not clear where you are having difficulty - your title and most of your question text is at odds with the code you provide. However the following code fixes various errors and fills in missing code. It generates the answer you want and uses Memoize to optimise viterbi's performance by caching results for given arguments lists.

use strict;
use warnings;
use Memoize qw();

my $trans = {
    'end' => {M2    => 1},
    'M2'  => {I1    => 0.1, M1 => 0.3},
    'I1'  => {begin => 0.8},
    'M1'  => {begin => 0.2},
    };

Memoize::memoize ('viterbi');
print viterbi('end', 3);


sub viterbi {
    my ($state, $output) = @_;

    return $output == 0 ? 1 : return 0
        if $state eq 'begin';

    return 0
        if $output == 0;

    my $r = $output - 1;
    my $max;
    
    for my $yy (keys %{$trans->{$state}}) {
        my $value = $trans->{$state}->{$yy} * viterbi($yy, $r);
        
        $max = $value if ! defined $max || $value > $max;
    }
    
    return $max;
}
[download]

Prints:

0.08
[download]