Recursion help!
Author Message
Recursion help!

Hello,
I have a question about recursions. Of all things I've done in
programming, recursion is *ONE* area that I simply cannot FULLY understand
for the love of God! I do understand recursions...but it gets hard to
track a recursive function. You know how it can get..heh. For example..if
I have a recursive functino to print a binary tree in in-order.. i
undestand it, and I can follow it..but it can get so complicating
sometimes..i lose track of where I am in the tracking. And when I code a
recursive function. I've coded a wildcard/string matching function using
iterative algorithm, but i'd like to understand it using recursions. Is
there an EASY way to understand recursions? It's one of those things that
I go.."Oh, I get it now!' then about 30 mintues later..i'm confused all
over again. An EASY way? Anyway? :) Thanks!

Wed, 15 Sep 1999 03:00:00 GMT
Recursion help!

Quote:

> Hello,
> I have a question about recursions. Of all things I've done in
> programming, recursion is *ONE* area that I simply cannot FULLY understand
> for the love of God! I do understand recursions...but it gets hard to
> track a recursive function. You know how it can get..heh. For example..if
> I have a recursive functino to print a binary tree in in-order.. i
> undestand it, and I can follow it..but it can get so complicating
> sometimes..i lose track of where I am in the tracking. And when I code a
> recursive function. I've coded a wildcard/string matching function using
> iterative algorithm, but i'd like to understand it using recursions. Is
> there an EASY way to understand recursions? It's one of those things that
> I go.."Oh, I get it now!' then about 30 mintues later..i'm confused all
> over again. An EASY way? Anyway? :) Thanks!

Welcome to the REAL world...

I did it myself, by using a de{*filter*} (Borlands IDE was good enough).
I needed a function to search a comma delimited string, for a match.
I did it with recursion, just for fun.

I wrote it from scratch, and stepped through it repeatedly, finding
many un-anticipated conditions (what we call "bugs").  When I was done,
I was satisfied with my understanding of recursion.

For me, it was one of those things I had to write myself, rather
than modify textbook code to see what it does.  That's what made
the difference.

-Scotty

Wed, 15 Sep 1999 03:00:00 GMT
Recursion help!

[>I have a question about recursions. Of all things I've done in
[>programming, recursion is *ONE* area that I simply cannot FULLY understand
[>for the love of God! I do understand recursions...but it gets hard to
[>track a recursive function. You know how it can get..heh. For example..if
[>I have a recursive functino to print a binary tree in in-order.. i
[>undestand it, and I can follow it..but it can get so complicating
[>sometimes..i lose track of where I am in the tracking. And when I code a
[>recursive function. I've coded a wildcard/string matching function using
[>iterative algorithm, but i'd like to understand it using recursions. Is
[>there an EASY way to understand recursions? It's one of those things that
[>I go.."Oh, I get it now!' then about 30 mintues later..i'm confused all

------- Well, unless you are absolutely forced to code recursively,
don't do it. Even though recorsive code is often much more shorter
and cleaner looking than iterative code, it is not pretty to debug
because of the problem of tracing it. One recursive function is not
too bad, but 2 or 3 functions that call each other recursively is
impossible. Tracing it and fixing/rewriting iteratively is just that
much harder.

if you want a good understanding of recursive functions, just write a
few yourself from scratch. They're just like pointers, you have to
use a few to have a good understanding of them. There are basically
2 components to recursion:

1 - recursive call (where the thing calls itself one or more times)
2 - base condition (this is where the calling sequence stops)

A good starting exercise might be to code recursively the
fibonacci sequence (1, 1, 2, 3, 5, 8, 13, 21...) where the
next number is a sum of the previous 2.
--
Mariusz Zydyk                           http://www.ucalgary.ca/~mszydyk/

Wed, 15 Sep 1999 03:00:00 GMT
Recursion help!

writes

Quote:
>sometimes..i lose track of where I am in the tracking. And when I code a
>recursive function. I've coded a wildcard/string matching function using
>iterative algorithm, but i'd like to understand it using recursions. Is
>there an EASY way to understand recursions? It's one of those things that
>I go.."Oh, I get it now!' then about 30 mintues later..i'm confused all
>over again. An EASY way? Anyway? :) Thanks!

Take the recursive leap of faith.

Ah!  Terrible mistake, to think the answer is "in the details".  You
don't "understand" recursion any better by hand tracing it, it just
seems to get more complicated, and more mysterious.

However, there is hope!  THE BEST book on recursion, which
demystifies it completely, is a small 1cm thick blueish paperback
"Thinking Recursively", with nested squares on the cover:

Author      :    Roberts, Eric.
Title       :    Thinking recursively / Eric Roberts.
Published   :    New York : J. Wiley, c1986.
Description :    179 p. : ill.
ISBN        :    0-47181-652-3 (pbk.)

It's in most University Libraries, under computer science.

Sandy

/*
--

//    Home Fone                 +44 (0) 171-794-4543
//    London, UK      http://www.almide.demon.co.uk/
*/

Wed, 15 Sep 1999 03:00:00 GMT
Recursion help!

Quote:
> Hello,
> I have a question about recursions. Of all things I've done in
> programming, recursion is *ONE* area that I simply cannot FULLY understand
> for the love of God! I do understand recursions...but it gets hard to
> track a recursive function. You know how it can get..heh. For example..if
> I have a recursive functino to print a binary tree in in-order.. i
> undestand it, and I can follow it..but it can get so complicating
> sometimes..i lose track of where I am in the tracking. And when I code a
> recursive function. I've coded a wildcard/string matching function using
> iterative algorithm, but i'd like to understand it using recursions. Is
> there an EASY way to understand recursions? It's one of those things that
> I go.."Oh, I get it now!' then about 30 mintues later..i'm confused all
> over again. An EASY way? Anyway? :) Thanks!

I think you're getting too bogged down in the abstraction of
recursion.

Here's a simple way of understanding recursion: You understand
having one subroutine call another subroutine, right?  Each
subroutine has its local set of variables, etc.  Say you have
a subroutine called "sub()", and it calls itself.  Pretend that
when sub() calls itself, the compiler creates a copy of the
source code of "sub" and assigns a unique name to it (like
sub2).  So, when it runs, sub is calling sub2.  Now, if sub calls
itself again (from within "sub2"), the compiler creates another
copy, and renames it to "sub3".

This is actually what happens, in a manner of speaking.  The
compiler maintains a separate set of variables for each nested
call to "sub", so that each call to the subroutine has a fresh
set of variables.  The areas are typically maintained in a stack
structure.

To be honest, if you really want to understand all this -- and
really understand it -- my recommendation is to learn assembly
language and look at the output of the compiler.  This will show
you the reality of what's going on, and you will learn more in
one week than a month of trying to wrestle with all these
abstractions.  I have a full justification of why learning assembly
language is the best way to learn programming on my web page, if
you are interested.

Good luck!

--
==========================================================================

| "Judge all, and be prepared to be judged by all."                      |
==========================================================================

Wed, 15 Sep 1999 03:00:00 GMT
Recursion help!

Quote:
> > Hello,
> > I have a question about recursions. Of all things I've done in
> > programming, recursion is *ONE* area that I simply cannot FULLY

understand
[...]

In a follow-up e-mail, it was further clarified that tracing recursive
functions was part of the problem.  I thought I would post part of my
answer on hints for debugging recursive routines...

[...]
As far as general hints for debugging recursive functions, I've found
the best way is to 1) print out what happens at each recursive level,
and 2) keep a global variable outside of the recursive function so
you know the depth.  I've that output to a trace file and then
reviewing the trace file is superior than trying to use a de{*filter*}
for recursive routines (but then, I find trace files to be superior
than de{*filter*}s for almost everything, but that's another subject

If you know the depth, you can do things like ...

#include <stdio.h>
#include <stdarg.h>

int Depth;

void DebugDump(int level, char *format, ...)
{
va_list arglist;

while (level--)
printf("  ");
va_start(arglist, format);
vprintf(format, arglist);
va_end(arglist);

Quote:
}

void Recurse(int i)
{
++Depth;
DebugDump(Depth, "i = %d\n", i);

if (i == 10) {
DebugDump(Depth, "Hit end! i = %d\n", i);
--Depth;
return;
}

DebugDump(Depth, "Calling Recurse with %d\n", i+1);
Recurse(i + 1);
DebugDump(Depth, "Returned when called with %d\n", i+1);
--Depth;
return;

Quote:
}

int main(void)
{
Recurse(1);
return(0)

Quote:
}

Note that the debug messages are indented to the level of the
recursive depth.  Incidently, having debug 'printf' style routines
like this are really helpful for debugging.  You can add timestamps
or whatever you want in the one central routine.

--
=========================================================================|

| "Judge all, and be prepared to be judged by all."                      |
=========================================================================|

Thu, 16 Sep 1999 03:00:00 GMT
Recursion help!

[Posted and mailed; crossposted to comp.programming for interest
and since there's hardly any C in here.]

Quote:

> ... Of all things I've done in programming, recursion is *ONE*
> area that I simply cannot FULLY understand for the love of God!
>  ...it gets hard to track a recursive function... it can get so
> complicating sometimes..i lose track of where I am in the tracking.
>...
> Is there an EASY way to understand recursions? It's one of those
> things that I go.."Oh, I get it now!' then about 30 mintues later..
> i'm confused all over again.

I'm going to make the, er, heretical suggestion that what you
might want to do is take the recursion just a little bit on
faith, and *not* try to understand it intimately.  If you try to
think about a particular recursive solution in detail, and
particularly if you try to think about it "all at once," you
really can get confused, and lose your place, and forget which
recursive level's arguments and variables you're thinking about
just now.

When I suggest that you "take it on faith" I of course don't mean
that you cough out any old seemingly recursive implementation and
blindly expect it to work.  Rather, the faith I'm talking about
is mostly the faith that a particular function is able to do its
job at all.  It's the essence of modularity that a function
should be a "black box," doing one job and doing it well.  When
another part of the program needs that one job done, it is
supposed to be able to call that function.  The caller is not
supposed to have to worry on that function's behalf; there aren't
supposed to be any circumstances under which that function can't
do that one job.  Functions are like the ultimate servants, and
their callers like the ultimate harsh, unsympathetic taskmasters.
It doesn't matter if the job is hard, or if it's one you couldn't
do yourself, or if you need 10,000 of them done (or one big one,
with 10,000 elements) -- when the job needs doing, it's the
function's job to do it, and there's no hook in the nice, narrow
functional interface which allows the function to complain that
you're working it too hard.

An essence of recursion is simply to be so "liberal" (or,
to continue the taskmaster metaphor, so ruthless) in our
interpretation of the "to do job X, call function Y" doctrine
that we're even willing to call function Y to do job X *within
the confines of function Y*.  After all, if we really believe
that we're allowed to call function Y to do job X *any time* we
need job X done, we shouldn't need to make any exceptions, even
if we're already in the middle of doing job X.  (Actually, of
course, we need to make one little exception, which I'll get to.)

which are on the web at http://www.eskimo.com/~scs/cclass/cclass.html.
Specifically, I discuss recursion in the "Notes to Accompany K&R",
sections 4.10 and 6.5.]

The idea of having a function call itself to do part of its job
seems like a crazy one at first.  However, it *can* work, in part
because it's possible to have several instances of a function
active simultaneously.  They don't interfere with each other,
because each instance has its own copies of its parameters and
local variables.  (However, if a function accesses any static or
global data, it must be written carefully if it is to be called
recursively, because then different instances of it *could*
interfere with each other.)

One example of a problem for which a recursive solution is
attractive is the problem of printing out decimal (or, for that
matter, any radix) representations of integers.  The obvious
algorithm for generating the digits is to repeatedly divide the
integer by 10 and take the successive remainders.  However, this
approach generates the digits in right-to-left order, while we'd
usually like them in left-to-right order, especially if we're
printing them out as we go.

Suppose we're trying to write a function to print the decimal
representation of an integer.  It's easy to find the lowest
(rightmost) digit; that's n % 10.  It's easy to compute all but
the lowest digit; that's n / 10.  So we could print a number
left-to-right, directly, without any explicit reversal step, if
we had a function to print all but the last digit.  We could call
that function, then print the last digit ourselves.

But -- here's the surprise -- the function to "print all but the
last digit" is the very same function we're already writing,
if we call it with an argument of n / 10 !

Recursion seems like cheating -- it seems that if you're writing
a function to do something (in this case, to print digits) and
instead of writing code to print digits you just punt and call a
function for printing digits and which is in fact the very
function you're supposed to write -- it seems like you haven't
done the job you came to do.  A recursive function seems like
circular reasoning; it seems to beg the question of how it does
its job.

But if you're writing a recursive function, as long as you do a
little bit of work yourself, and only pass a smaller portion of
the job on to another instance of yourself, you haven't
completely reneged on your responsibilities.  Furthermore, if
you're ever called with such a small job to do that the little
bit you're willing to do encompasses the whole job, you don't
have to call yourself again at all (there's no remaining portion
that you can't or won't do).  Finally, since each recursive call
does some work, passing on smaller and smaller portions to
succeeding recursive calls, and since the last call (where the
remaining portion is empty) doesn't generate any more recursive
calls, the recursion is broken and doesn't constitute an infinite
loop.

Another -- in fact, the classic -- example of a recursive
function is a function for printing the nodes of a binary tree,
in order.  Suppose it's our job to print a binary tree: we've
just been handed a pointer to the base (root) of the tree.  What
do we do?  The only node we've got easy access to is the root
node, but it's *not* the first or the last element to print or
anything; it's generally a random node somewhere in the middle of
the eventual sorted list (distinguished only by the fact that it
happened to be inserted first).  The node that needs to be
printed first is buried somewhere down in the left subtree, and
the node to print just before the node we've got easy access to
is buried somewhere else down in the left subtree, and the node
to print next (after the one we've got) is buried somewhere down
in the right subtree.  In fact, everything down in the left
subtree is to be printed before the node we've got, and
everything down in the right subtree is to be printed after.
A pseudocode description of our task, therefore, might be

print the left subtree (in order)
print the node we're at
print the right subtree (in order)

How can we print the left subtree, in order?  The left subtree
is, in general, another tree, so printing it out sounds about as
hard as printing an entire tree, which is what we were supposed
to do.  In fact, it's exactly as hard: it's the same problem.
Are we going in circles?  Are we getting anywhere?  Yes, we are:
the left subtree, even though it is still a tree, is at least
*smaller* than the full tree we started with.  The same is true
of the right subtree.  Therefore, we can use a recursive call to
do the hard work of printing the subtrees, and all we have to do
is the easy part: print the node we're at.  The fact that the
subtrees are smaller gives us the leverage we need to make a
recursive algorithm work.

[end of text derived from class notes]

"Believing" in a recursive algorithm is a lot like believing in
proof by induction.  You can't really look at all the steps, all
at once, and try to "grok" them in fullness, because there is an
arbitrary (and essentially infinite) number of steps in the
general case.  Instead, what you have to do is:

1. *Believe* in the general process.  For an inductive
proof, the general process is that you prove the theorem
for case N=1, and you prove that *if* the theorem is true
for case N, *then* it must also be true for case N+1, and
presto, the entire towering edifice of a proof, for
N=anything, spontaneously erects itself almost as
magically as a block of flats put up by the Amazing
Mystico and Janet.  For a recursive algorithm, the
general process is that a function calls itself to do
part of its job, making sure that it either calls itself
with a strictly smaller portion of the job to do, or that
(when the job is so simple that the function can do it
"all by itself"), it doesn't call itself, after all.

2. *Show* that a particular instance (of an inductive proof
or a recursive implementation) meets the qualifications
described in (1).  In the case of an inductive proof, you
have to really prove the theorem for N=1 (and no fair
just assuming or postulating it), and you have to
rigorously prove that N implies N+1 (and no fair using a
shoddy proof, such as one that works for any N except 2).
For a recursive implementation, you have to show that
whenever the function calls itself, it is always on a
strictly smaller subtask of the main job, and that for
sufficiently small subtasks, the function does the work
itself and returns immediately.  (Also, you have to make
sure that the function doesn't use any static data, or
that if it does, it's carefully contrived to be valid
under recursion.)

In my classes, we used to play a game to demonstrate recursion
in a hands-on way.  I wrote up an English (as opposed to C)
implementation of the recursive tree-print function, and handed
copies to all the students.  I made up a "tree" built out of
those little yellow stickie notes, with words written on each of
them, stuck together in such a way that when you peeled the top
one off, you were left with two subtrees.  The students'
"program" ...

Fri, 17 Sep 1999 03:00:00 GMT
Recursion help!

Quote:

> > ... Of all things I've done in programming, recursion is *ONE*
> > area that I simply cannot FULLY understand for the love of God!
> > Is there an EASY way to understand recursions? It's one of those
> > things that I go.."Oh, I get it now!' then about 30 mintues later..
> > i'm confused all over again.

> I'm going to make the, er, heretical suggestion that what you
> might want to do is take the recursion just a little bit on
> faith, and *not* try to understand it intimately.

<snip>

Quote:
> Rather, the faith I'm talking about
> is mostly the faith that a particular function is able to do its
> job at all.  It's the essence of modularity that a function
> should be a "black box," doing one job and doing it well.

<lots of stuff sniped>

WOW, what a superb explanation of understanding recursion [see original post].

You might also consider the value of formal methods for understanding
things in this 'black box' since.

Jimmy

Fri, 17 Sep 1999 03:00:00 GMT
Recursion help!

Quote:

> > > Hello,
> > > I have a question about recursions. Of all things I've done in
> > > programming, recursion is *ONE* area that I simply cannot FULLY
> understand
> [...]

> In a follow-up e-mail, it was further clarified that tracing recursive
> functions was part of the problem.  I thought I would post part of my
> answer on hints for debugging recursive routines...

> [...]
> As far as general hints for debugging recursive functions, I've found
> the best way is to 1) print out what happens at each recursive level,
> and 2) keep a global variable outside of the recursive function so
> you know the depth.  I've that output to a trace file and then
> reviewing the trace file is superior than trying to use a de{*filter*}
> for recursive routines (but then, I find trace files to be superior
> than de{*filter*}s for almost everything, but that's another subject
> for another thread...)

> If you know the depth, you can do things like ...

> #include <stdio.h>
> #include <stdarg.h>

> int Depth;

> void DebugDump(int level, char *format, ...)
> {
>     va_list arglist;

>     while (level--)
>         printf("  ");
>     va_start(arglist, format);
>     vprintf(format, arglist);
>     va_end(arglist);
> }

> void Recurse(int i)
> {
>     ++Depth;
>     DebugDump(Depth, "i = %d\n", i);

>     if (i == 10) {
>         DebugDump(Depth, "Hit end! i = %d\n", i);
>         --Depth;
>         return;
>     }

>     DebugDump(Depth, "Calling Recurse with %d\n", i+1);
>     Recurse(i + 1);
>     DebugDump(Depth, "Returned when called with %d\n", i+1);
>     --Depth;
>     return;
> }

> int main(void)
> {
>     Recurse(1);
>     return(0);
> }
> Note that the debug messages are indented to the level of the
> recursive depth.  Incidently, having debug 'printf' style routines
> like this are really helpful for debugging.  You can add timestamps
> or whatever you want in the one central routine.

Thank you for this, it is most helpful.

--
********************************************

********************************************
The money spent on an {*filter*},
as any woman may find out,
can better be spent on other things,
like taking the kids to an amusment park, or on vacation.

Fri, 17 Sep 1999 03:00:00 GMT
Recursion help!

: > Hello,
: > I have a question about recursions. Of all things I've done in
: > programming, recursion is *ONE* area that I simply cannot FULLY understand
: > for the love of God! I do understand recursions...but it gets hard to
: > track a recursive function. You know how it can get..heh. For example..if
: > I have a recursive functino to print a binary tree in in-order.. i
: > undestand it, and I can follow it..but it can get so complicating
: > sometimes..i lose track of where I am in the tracking. And when I code a
: > recursive function. I've coded a wildcard/string matching function using
: > iterative algorithm, but i'd like to understand it using recursions. Is
: > there an EASY way to understand recursions? It's one of those things that
: > I go.."Oh, I get it now!' then about 30 mintues later..i'm confused all
: > over again. An EASY way? Anyway? :) Thanks!

It's like proof by induction... which I ALSO find very confusing.  But
basically I never try to fully understand what a recursive function
does... what I do instead is figure out what the rules are for what I
want to do.  For example if going through a tree recursively,  what I
want to do is do something to the current branch, then do the same thing
to the left branch and to the right branch.  But when I get to the left
branch and right branch I want it to act exactly the same way as it did
on this branch... that is do something to the now-current left or right
branch and then look at THEIR left or right branches.  At this point I
need go no further, I have come up with the general rule for a branch:
do something to it and then recursively call the function for each of
its left and right branches which will do something to them and then
recursively call the function for each of their left and right branches
and so on ad-infinitum.

That is by the way one of THE basic uses of recursion, tree searching.
IT might do you worlds of good to study that particulr case until
you understand it well...  then go on to more esoteric uses of the
recursion method as required.

David

Mon, 27 Sep 1999 03:00:00 GMT

 Page 1 of 1 [ 10 post ]

Relevant Pages