R(0)  = 0;
for n > 0,
    R(n) = R(n-1) - n if positive and not already in the sequence, otherwise
    R(n) = R(n-1) + n.

##</code><code>##

use strict;
use warnings;
use constant MAX => 1e6;

$| = 1;

my %seq = (0 => 0);
my $r0  =  0;

for my $n (1 .. MAX)
{
    my $r = $r0 - $n;
       $r = $r0 + $n if $r < 0 || exists $seq{$r};

    $seq{$r} = $n;
    $r0      = $r;
}

for (0 .. MAX)
{
    unless (exists $seq{$_})
    {
        printf "For MAX = %.1e, the first missing number is %d\n", MAX, $_;
        last;
    }
}

##</code><code>##

14:20 >perl recaman.pl
1 <-- 1
2 <-- 4
4 <-- 131
19 <-- 99734
...

##</code><code>##

use strict;
use warnings;
use sigtrap handler => \&int_handler,   'INT',
            handler => \&break_handler, 'BREAK';
use Set::IntSpan;
use Time::HiRes qw(gettimeofday tv_interval);

   $|       = 1;
my $t0      = [gettimeofday];
my $min0    = 1;
my $n       = 0;
my $r0      = 0;
my $missing = Set::IntSpan->new( '1-)' );

print "$min0 <-- ";

while (++$n)
{
    my $r = $r0 - $n;
       $r = $r0 + $n if $r < 0 || !$missing->member($r);

    $missing->remove($r);

    if ((my $min1 = $missing->min) > $min0)
    {
        print "$n\n$min1 <-- ";
        $min0 = $min1;
    }

    $r0 = $r;
}

sub int_handler
{
    printf "\nn = %d, elapsed time: %.1fs\n", $n, tv_interval($t0);
}

sub break_handler
{
    int_handler();
    exit 0;
}

##</code><code>##

14:20 >perl -v

This is perl 5, version 22, subversion 0 (v5.22.0) built for MSWin32-x64-multi-thread