Perl-Sensitive Sunglasses PerlMonks

### Visualizing recursion with the fib() example

by stevieb (Abbot)
 on Mar 18, 2012 at 00:41 UTC 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

Replies are listed 'Best First'.
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 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)

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 ... )

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
Re: Visualizing recursion with the fib() example
by stevieb (Abbot) on Mar 18, 2012 at 02:08 UTC

Spectacular! Thanks all!

This was exactly the kick I needed :)

Steve

Create A New User
Node Status?
node history
Node Type: perlquestion [id://960230]
Approved by McDarren
help
Chatterbox?
Jar. Jar!...

How do I use this? | Other CB clients
Other Users?
Others wandering the Monastery: (3)
As of 2018-01-20 04:27 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
How did you see in the new year?

Results (226 votes). Check out past polls.

Notices?