Visualizing recursion with the fib() example

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

While I'm at it today, I figure I may as well bow again to our Glorious Monks.

Recursion to some is a simple topic to tackle mathematically, but I have had a very difficult time visually comprehending the timeless fib() example. I don't know why, but I just can't grasp how the end result becomes, because I can't exactly identify how the top-level call enumerates its value.

To the best of my ability, I've tried to print everything out, but I *still* can't grasp what is returned to what, and on what basis a fib(N) call figures out the final figures. I have (semi-broken) code below that I wrote to help me follow codeflow, but I almost need a picture.

I don't mind being the only one who just can't grasp this, or the only one who has spoken up. Any type of figurative help would be immensely appreciated:

#!/usr/bin/perl

use warnings;
use strict;

fib( 5, 0 );

my $count = 0;
my $sub_1_count = 0;
my $sub_2_count = 0;

sub  fib  { 

    my  $num            = shift; 
    my  $recurse_sub    = shift;

    $count++;

    print "\nEntering main\n";
    print "Iteration: $count\n";
    print "Call: sub($recurse_sub)\n";
    print "Working num: $num\n";

    if  ($num <= 2) {  

        print "Returning 1 called by fib($recurse_sub)\n";
        return 1;
    } 
     else   { 

         $sub_1_count++;
         print "Entering fib($recurse_sub), call $sub_1_count\n";
         my $x = fib($num-1, -1);  
         
         $sub_2_count++;
         print "Entering fib($recurse_sub), call $sub_2_count\n";
         my $y = fib($num-2, -2); 

         print "Returning fib(-1) + fib(-2)\n";
         print "Result: $x $y\n";

         return $x + $y; 
      } 
}
[download]

Anything you can add to spark an *OMFG* realization appreciated

Comment on Visualizing recursion with the fib() example Download Code

Replies are listed 'Best First'.
Re: Visualizing recursion with the fib() example by BrowserUk (Patriarch) on Mar 18, 2012 at 01:31 UTC
Does this help? c:\test>fib 7 13 fib( 7 ) ->fib( 6 ) + fib( 5 ) .fib( 6 ) ->fib( 5 ) + fib( 4 ) . .fib( 5 ) ->fib( 4 ) + fib( 3 ) . . .fib( 4 ) ->fib( 3 ) + fib( 2 ) . . . .fib( 3 ) ->fib( 2 ) + fib( 1 ) . . . . .fib( 2 ) -> 1 . . . . .fib( 1 ) -> 1 . . . .fib( 2 ) -> 1 . . .fib( 3 ) ->fib( 2 ) + fib( 1 ) . . . .fib( 2 ) -> 1 . . . .fib( 1 ) -> 1 . .fib( 4 ) ->fib( 3 ) + fib( 2 ) . . .fib( 3 ) ->fib( 2 ) + fib( 1 ) . . . .fib( 2 ) -> 1 . . . .fib( 1 ) -> 1 . . .fib( 2 ) -> 1 .fib( 5 ) ->fib( 4 ) + fib( 3 ) . .fib( 4 ) ->fib( 3 ) + fib( 2 ) . . .fib( 3 ) ->fib( 2 ) + fib( 1 ) . . . .fib( 2 ) -> 1 . . . .fib( 1 ) -> 1 . . .fib( 2 ) -> 1 . .fib( 3 ) ->fib( 2 ) + fib( 1 ) . . .fib( 2 ) -> 1 . . .fib( 1 ) -> 1 13 [download] Produced by #! perl -slw use strict; sub fib { my $n = shift; return 1 if $n == 1; return 1 if $n == 2; return fib( $n - 1 ) + fib( $n - 2 ); } my $indent = -1; sub fibx { ++$indent; my $n = shift; my $ret; if( $n == 1 ) { printf "%sfib( %d ) -> 1\n", ' .' x $indent, $n; $ret = 1; } elsif( $n == 2 ) { printf "%sfib( %d ) -> 1\n", ' .' x $indent, $n; $ret = 1; } else { printf "%sfib( %d ) ->fib( %d ) + fib( %d )\n", ' .' x $inden +t, $n, $n-1, $n-2; $ret = fibx( $n - 1 ) + fibx( $n - 2 ); } --$indent; return $ret; } print fib( $ARGV[ 0 ] ); print fibx( $ARGV[ 0 ] ); [download] With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday' Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error. "Science is about questioning the status quo. Questioning authority". In the absence of evidence, opinion is indistinguishable from prejudice. The start of some sanity?	[reply] [d/l] [select]
Re: Visualizing recursion with the fib() example by Anonymous Monk on Mar 18, 2012 at 00:51 UTC
Anything you can add to spark an OMFG* realization appreciated* Forget about computers and grab pencil and paper, and writeout the formula for fib(0), fib(1), fib(2), fib(3), fib(4), fib(5)	[reply]
Re^2: Visualizing recursion with the fib() example by Anonymous Monk on Mar 18, 2012 at 01:25 UTC
A good introduction to recursion is Higher-Order Perl Chapter 1: Recursion and Callbacks. The walk-through starts simple with binary numbers, then moves on to directory traversal, the meat and potatoes of recursion :) A quick foray into html tree traversal (just like directory tree, trees are the meat and potatoes ) and it ends with Fibonacci in section 1.8 When Recursion Blows Up Devel::TraceCalls shows the tree (book one or two nice pics) #!/usr/bin/perl -- use strict; use warnings; use Devel::TraceCalls { Subs => [qw/fib /]}; print fib(5); sub fib { my $n = shift; if ($n < 2) { return $n } fib($n-2) + fib($n-1); } __END__ TRACE: main::fib( 5 ) TRACE: +-main::fib( 3 ) TRACE: \| +-main::fib( 1 ) TRACE: \| +-main::fib( 2 ) TRACE: \| ! +-main::fib( 0 ) TRACE: \| ! +-main::fib( 1 ) TRACE: +-main::fib( 4 ) TRACE: \| +-main::fib( 2 ) TRACE: \| ! +-main::fib( 0 ) TRACE: \| ! +-main::fib( 1 ) TRACE: \| +-main::fib( 3 ) TRACE: \| ! +-main::fib( 1 ) TRACE: \| ! +-main::fib( 2 ) TRACE: \| ! \| +-main::fib( 0 ) TRACE: \| ! \| +-main::fib( 1 ) 5 [download] If you made a directory mimicking fib-5 you can see the tree in your file browser Read more... (554 Bytes) Or with tree fib-5 \|-- fib-3 \| \|-- fib-1 \| `-- fib-2 \| \|-- fib-0 \| `-- fib-1 `-- fib-4 \|-- fib-2 \| \|-- fib-0 \| `-- fib-1 `-- fib-3 \|-- fib-1 `-- fib-2 \|-- fib-0 `-- fib-1 [download] Chapter 5: From Recursion to Iterators, deals with Eliminating Recursion from fib ( see fib-0, fib-1, fib-2 ... )	[reply] [d/l] [select]
Re^2: Visualizing recursion with the fib() example by stevieb (Canon) on Mar 18, 2012 at 00:55 UTC
I understand the mathematical equations entirely... what I can't grasp is how Perl is handling the recursion. Perhaps it is as simple as the math, but it just ain't 'clicking', hence my question.	[reply]
Re^3: Visualizing recursion with the fib() example by Anonymous Monk on Mar 18, 2012 at 01:33 UTC
I understand the mathematical equations entirely... what I can't grasp is how Perl is handling the recursion. Perhaps it is as simple as the math, but it just ain't 'clicking', hence my question. Um, yes, its exactly like the math. It didn't click for me either until I wrote it out by hand with a pencil. `#!/usr/bin/perl -- use strict; use warnings; print fib(5); sub fib { my( $n, $depth ) = @_; $depth \|\|= 0; print "(d $depth)", " " x $depth, " (n $n)\n"; if ($n < 2) { return $n } fib($n-2, $depth + 1 ) + fib($n-1 , $depth + 1 ); } __END__ (d 0) (n 5) (d 1) (n 3) (d 2) (n 1) (d 2) (n 2) (d 3) (n 0) (d 3) (n 1) (d 1) (n 4) (d 2) (n 2) (d 3) (n 0) (d 3) (n 1) (d 2) (n 3) (d 3) (n 1) (d 3) (n 2) (d 4) (n 0) (d 4) (n 1) 5` [download]	[reply] [d/l]
Re: Visualizing recursion with the fib() example by stevieb (Canon) on Mar 18, 2012 at 02:08 UTC
Spectacular! Thanks all! This was exactly the kick I needed :) Steve	[reply]