[prog] functions

[Cliff Crawford]

On Mon, Jan 12, 2004 at 04:08:03AM -0500, wolf wrote:
> Hello : )
> 
> I am still trying to learn C++ and was wondering if anyone could offer 
> some very basic explanations for a couple things.  What is the 
> difference between recursion and iteration
> and why would you chose to use one over the other?

Recursion is often useful when you have some kind of a tree structure
and you want to perform an operation on every element.  What you do is
write a procedure which takes a node as an argument, and for all of
the children of the node test if they are leaves or nodes.  If they
are nodes, then you recursively call the procedure with it as the new
argument.  Then call your procedure with the root node as the initial
argument to get the whole thing started.  For example, if you wanted
to print out all of the nodes of a tree, you could do something like
the following (in pseudocode):

define tree-printer (node):
	left = left-child(node)
	right = right-child(node)

	if (is-node(left)):
		tree-printer(left)
	else:
		print(left)

	if (is-node(right)):
		tree-printer(right)
	else:
		print(right)

It's possible to do this with iteration too, but it would be more
complicated because as you were going through the loop you would have
to keep track of all the nodes you've seen in a queue or stack, so
that you can go back and print all of their children's nodes, etc.
Using recursive calls does this bookkeeping for you implicitly, using
the call stack.

Iteration *is* useful, though, for doing the same sort of thing on a
linear date structure, like a list.  For example, a procedure to print
out all the elements in a list is easy to write with a simple loop:

define list-printer (list):
	for each element in list:
		print element

You could write the same procedure using recursion instead, as follows:

define list-printer (list):
	if (not empty(list))):
		print head(list)
		list-printer(tail(list))

But then it will be harder to see what it's actually doing (since most
people find recursion a bit confusing ;), and it might be inefficient
too, depending on how your compiler handles tail-recursion.


> Also, can anyone 
> give me
> an example of what an inline function is and why it would be used?  
> Just really simple
> basic answers if anyone has the time : )

An inline function is a function which will be "inlined" (incorporated
into the calling function) when you compile.  This is useful for small
functions which need to be executed really fast (if you're in an inner
loop, for example).  For example, suppose you had a function "square"
which returned the square of its argument:

define square (x):
	return x*x

If you declare "square" to be inline, then the compiler will transform
all calls to "square" like so:

...blah...                      ...blah...
y = square(y)        ==>        y = y*y
...blah blah...                 ...blah blah...

However, you usually don't need to worry about inlining functions (or
other optimizations) until after you've got a working version of your
program, and you profile it to know which parts of your code are
taking the most time to run.  (Note the quote in my signature. ;)


-- 
 Cliff Crawford            ***            cjc26 at cornell.edu
"But I also knew, and forgot, Hoare's dictum that premature
 optimisation is the root of all evil in programming."
                               -- Knuth, "The Errors of TeX"