Recursive function

There are two types of recursive functions in programming. There is direct recursion, where a function calls itself from within its own body, and indirect recursion where a function calls a second function which in turn calls the first function again.

Most programming books will teach recursion by using it to solve problems such as exponential statements and fibonacci numbers. The fact is, these problems usually have simpler solutions than recursion, which is often bulky, slow, hard to read, or first and foremost a memory eater.

Occasionally, however, recursion is the best solution. If you can't solve the problem using loops, try recursion, but be careful.

Mathematically, a recursive function is a function that defines itself in terms of itself. No, it's not as hopelessly confusing as it appears.

for instance, take this function:
f(n)=4*f(n-1)
This would be impossible to compute unless you set a lower limit, such as f(1)=1...
In that case, you'd get the following values.

in | out
1  | 1
2  | 4
3  | 16
4  | 64
...

This gets annoying, however, if you need to find a term that is greater than about five, in which case, you are buried in numbers. Then, you turn to a programmable calculator.
Even though functions are typically referred to as f(x), to show that it is a recursive function, it is standard to use n instead.

Recursive functions can define themselves in terms of the previous (or next, in which case you'd need to define upper limits) TWO (or more, to infinity) functions... such as:
f(n)=3*f(n-1) - f(n-2)
f(0)=0; f(1)=2=
which would give the following results:

in |out
0  |0
1  |2
2  |6
3  |16
4  |46
5  |138
...

if ( noder.isInterested() ) {

 cout << "See recursive function";
} else if ( noder.isBored() ) {

cout << "A function that uses the programming technique of recursion";

cout << "i.e. calls itself until some internal condition is satisfied";
}

I guess I´ll have to show you an example, this is is a Perl subroutine I´ve used to edit some filelevel permissions.

sub find_files						 
{
    if ($_0 =~ /.[\/]$/){				
    	$_ = "$_[ 0 ]*";
      	} else {
    		  $_ = "$_[ 0 ]/*";
    		}
    
    my @directory,$i; 				
    @files = glob;           			      
    
    $i = 0;							 
       
    foreach $file (@files){			
       if (-d $file){				         
       $directory[$i] = $file;		      
         	$i++;        				 
 	    } else {						
			HERE_U_DO_STUFF_WITH_THE $file 								
    		    }
    }
    foreach $dir (@directory){
    	find_files($dir);
    }
}

And now, for your excitement, the Fibonacci sequence:
f(n) = f(n-1) + f(n-2); f(0) = f(1) = 1.

While we're at it, here's a nifty sequence from Gödel, Escher, Bach: An Eternal Golden Braid:
g(n)=n-g(g(n-1)); g(0)=0.

Whee. . .. ... ..... ........ ............. .................... ..................................

I had a hell of a time understanding recursion back in my salad days, and didn't really come to grasp it fully until I was forced to learn Lisp (Which I highly recommend, by the way). In the hopes of easing the road to this understanding for some future, budding Comp-Sci geek, here's just about the simplest useful recursive function I know, written in Ruby, just about the simplest useful programming language I know.

def factorial(num)
    if num == 0
        return 1
    else
        return num * factorial(num - 1)
    end
end

Since that won't mean much unless you're already familiar with the ideas behind recursion, we'll step through it using an example.

Say we called this function on the number 4. Anyone who had to learn factorials in school knows that 4! = 4 * 3 * 2 * 1 = 24. What we need to tell our program to do, then, is multiply 4 times 4-1 times (4-1)-1, etc . . . down to 1. Most of this is accomplished through this line:

return num * factorial(num - 1)

What confused me most about recursive functions was figuring out just where in Hell the "work" was getting done. All I saw were a bunch of function calls and a stopping condition! The trick is to pay close attention to those function calls, and look at the arguments they're being passed. In this case, we're calling factorial all over again, but this time we're calling it on 4-1. So what we have on our program stack right now is:

factorial(4)
    factorial(3)

It will be called two more times before the stopping condition, which is num equal to 1, is met. Now, when we reach the stopping condition is when the real magic happens. We've got our program stack looking like so:

factorial(4)
    factorial(3)
        factorial(2)
            factorial(1)

and we've reached the point where num is equal to 1. Our program will then return the number 1, just as it's been told to, and unwind the recursion. If you remember our workhorse statement (return num * factorial(num - 1)), you'll recall that it starts with a return. What it's doing is returning the value of whatever num currently is times whatever the previous function returned. It's probably easier to visualize this than explain it:

factorial(4)
^   factorial(3)
|   ^   factorial(2)
|   |   ^   factorial(1)
|   |   ----returns 1
|   ----returns 2 * 1
----returns 3 * 2
returns 4 * 6

So factorial(1), seeing that num is equal to 1, returns 1. Control then passes to the next function on the stack, which is factorial(2). This function returns using the statement return num * factorial(num - 1). Substituting the numbers we know we have into this statement, we get return 2 * 1(1 coming from the previous return statement). The next function up the stack is factorial(3), which receives whatever factorial(2) returned, so it returns 3 * 2, and finally our first function call gets to return, using the result of all those function calls that came before it, returning 4 * 6, which is 24 (Notice that we employed the Distributive Property of multiplication for this. Hooray for maths!)

My hope is that this little example was helpful to someone in coming to understand how to read and create recursive functions. If this by some miracle sparked an interest, I'd recommend learning Lisp to explore recursion more fully, mainly because it's dead-easy to recurse with. Good luck, my friends! Curse, and curse again!