Beefy Boxes and Bandwidth Generously Provided by pair Networks
The stupid question is the question not asked
 
PerlMonks  

Visualizing recursion with the fib() example

by stevieb (Hermit)
on Mar 18, 2012 at 00:41 UTC ( #960230=perlquestion: print w/ replies, xml ) Need Help??
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; } }

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

Comment on Visualizing recursion with the fib() example
Download Code
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)

      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.

        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

      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

      If you made a directory mimicking fib-5 you can see the tree in your file browser

      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

      Chapter 5: From Recursion to Iterators, deals with Eliminating Recursion from fib ( see fib-0, fib-1, fib-2 ... )

Re: Visualizing recursion with the fib() example
by BrowserUk (Pope) 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

    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 ] );

    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?

Re: Visualizing recursion with the fib() example
by stevieb (Hermit) on Mar 18, 2012 at 02:08 UTC

    Spectacular! Thanks all!

    This was exactly the kick I needed :)

    Steve

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://960230]
Approved by McDarren
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others meditating upon the Monastery: (11)
As of 2014-07-30 15:17 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    My favorite superfluous repetitious redundant duplicative phrase is:









    Results (235 votes), past polls