### Re: recursion basics

by aaron_baugher (Curate)
 on Jun 23, 2015 at 06:32 UTC ( #1131569=note: print w/replies, xml ) Need Help??

With recursion, a function can call itself, and each call creates a new copy of the function, complete with its own local variables. Each time the function calls itself, the first instance of it stops and waits for the second one to finish -- which may call a third instance and wait for that to finish, and so on.

In the case of your example, the first call to binary() creates a running copy of the function (let's call it binary1) and passes it the value 8. It calculates a few things and sets a few variables which are local to this instance (\$n, \$k, \$b). Then it makes a call to binary(), passing it the value 4. This creates a second running copy of binary() (binary2), which will have its own copy of those variables (\$n, \$k, \$b), completely separate from binary1's copies. As soon as binary2 is called, binary1 stops and waits for it to return.

So now binary2 is running, and goes through the same process of setting variables, except that this time the values are different because it was called with a different argument. It gets down to a third call to binary(), to which it now passes \$k = 2. Now binary2 stops and waits for this third copy (binary3) to return. Binary3 sets its own copies of the variables, and passes the value 1 to a fourth call to binary() (binary4), while binary3 stops and waits for binary4 to return.

Now there are four copies of the binary() function running, each with its own local copies of several variables, and the first three each waiting on the next to finish. When binary4 hits the return() line, the test returns true this time (\$n==1), so the whole thing starts unspooling. Binary4 returns \$n back to binary3, which puts that value in \$E and continues where it stopped. When binary3 gets to its last instruction and returns, binary2 picks up where it stopped by setting \$E to the return value of binary3. Binary2 finishes and returns, letting binary1 set \$E to the return value of binary2. Binary1 (the very first call to the function) now continues and finishes, and passes its own return value to print().

Recursion can be hard to get a grip on at first, but step through the process one step at a time, keeping in mind that each new call to the function creates a new copy of it, with its own copy of any my/local variables. Remember that each time the function calls itself, the caller stops and waits for the called to return. If necessary, draw it out on paper, making a separate box for each copy of the function, writing its variables inside it, with arrows to point from each copy back to the point in its caller where it will return to.

Aaron B.
Available for small or large Perl jobs and *nix system administration; see my home node.

Replies are listed 'Best First'.
Re^2: recursion basics
by wrinkles (Pilgrim) on Jun 23, 2015 at 06:49 UTC
Wow, nice explanation. I'll get a good night's rest and read that again slowly, and yes draw a diagram. Thanks to all for your help!

Create A New User
Node Status?
node history
Node Type: note [id://1131569]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others wandering the Monastery: (3)
As of 2020-06-05 04:09 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
Do you really want to know if there is extraterrestrial life?

Results (35 votes). Check out past polls.

Notices?