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

In reply to Visualizing recursion with the fib() example by stevieb

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.