How do I return from an anonymous recursive sub in perl6?

Three more options:

sub

You can write anonymous routines by using sub without a name:

my $fib = sub (Int $x --> Int) {
  return 0 if $x == 0;
  return 1 if $x == 1;
  return $fib($x - 1) + $fib($x - 2); 
}

say $fib(13); # 233

See @HåkonHægland's answer for why this (deliberately) doesn't work with non-routine blocks.

leave

The design anticipated your question:

my $fib = -> Int $x --> Int {
  leave 0 if $x == 0;
  leave 1 if $x == 1;
  leave $fib($x - 1) + $fib($x - 2); 
}

compiles. Hopefully you can guess that what it does -- or rather is supposed to do -- is exactly what you wanted to do.

Unfortunately, if you follow the above with:

say $fib(13);

You get a run-time error "leave not yet implemented".

My guess is that this'll get implemented some time in the next few years and the "Attempt to return outside of any Routine" error message will then mention leave. But implementing it has very low priority because it's easy to write sub as above, or write code as @HåkonHægland did, or use a case/switch statement construct as follows, and that's plenty good enough for now.

case/switch (when/default)

You can specify the parameter as $_ instead of $x and then you're all set to use constructs that refer to the topic:

my $fib = -> Int $_ --> Int {
  when 0 { 0 }
  when 1 { 1 }
  $fib($_ - 1) + $fib($_ - 2)
}

say $fib(13); # 233

See when.

Blocks don't need to declare the return type. You can still return whatever you want, though. The problem is not in using return, it's in the declaration of the Int.

use v6;

my $fib = -> Int $x  {
    if $x == 0 {
        0;
    } elsif $x == 1 {
        1;
    } else {
        $fib($x - 1) + $fib($x - 2);
    }
}

say $fib(13) ;

The problem is that the return value needs to be the last executed. In the way you have done it, if it finds 0 or 1 it keeps running, getting to the last statement, when it will start all over again. Alternatively, you can use given instead of the cascaded ifs. As long as whatever it returns is the last issued, it's OK.

According to the documentation :

Blocks that aren't of type Routine (which is a subclass of Block) are transparent to return.

sub f() {
say <a b c>.map: { return 42 };
               #   ^^^^^^   exits &f, not just the block  }

The last statement is the implicit return value of the block

So you can try:

my $fib = -> Int $x --> Int {
    if ( $x == 0 ) {
        0;  # <-- Implicit return value
    }
    elsif ( $x == 1 ) {
        1;  # <-- Implicit return value
    }
    else {
        $fib($x - 1) + $fib($x - 2);  # <-- Implicit return value
    }
}