dan_e6

I read somewhere about a function/subrountine calling itself. i dunno how this works or if i mis-read it but can anyone explain how it works and what u would use it for ?

Diurnal

I believe what you are asking about is called recursion. A routine may do some work and call itself to do more work. There is an article on Using Recursion to Search a Directory in the knowledge base that might be useful for giving an example of the concept.

loquin

The classic example of this (recursion) is the calculation of factorial numbers.

The factorial numbers are defined such that the factorial of a natural number n is the product of all positive integers less than or equal to n. The fifth number in the series is thus 5 * 4 * 3 * 2 * 1. The 6th numnber is 6 * 5 * 4 * 3 * 2 * 1. And, so on.

If you look at these two series though, you will see that the 6th number is equal to 6 * the 5th factorial. And, so on.

So, you could easily write a factorial function that is recursive.

For instance


This function will recursively call itself. You just have to ensure that a recursive function has an "exit" - else it will recursively call itself until it ties up all avaialble memory, and then it will crash. (Note that the results of this function grow so quickly as N increases that it will overflow a long variable type when N = 12! As a result, you will probably want to use doubles, instead of longs. Also note that the factorial function is also one that is easy to write non-recursively as well, using a loop within the function.)

Recursion is often used when each task you are performing is essentially identical to that "above" it

Dinural mentioned searching a directory. Each subdirectory can be called by the same routine. Which will call the dir routine for each subfolder... And, so on.

Another example of a "natural" fit for recursion is in a binary search.

In a binary search, you are searching for a match in an ordered list. You start by setting the min and max limits to search, picking a midpoint in the list that is halfway between the min and max, and check to see if the value at that midpoint is = to, less than, or greater than the one you're looking for.

If it's equal, then you are done - you have a match. Huzzah! And exit.

If the value at this position is less than your target value, then you must go higher - set the min value to the current midpoint, pick a new mid-point halfway between the new min and the existing max limits, and call the binary search routine with these new values.

On the other hand, if the value at this position is greater than your target value, then the match, if it exists, is less than where your're at, so set the max limit to the current position, set the midpoint to halfway between the min and the max, and call the binary search routine again.

If max-min = 1 and you haven't found a target value, then it isn't in the list.

Edit by loquin:

Quote:

Originally Posted by Elder Knight I believe that Loquin's example illustrates the factorial function, not a Fibonacci Series....

D'Oh! Yup - you're exactly right! I'll fix that!

DougT

One of the most common mistakes, when programming recursive routines, is to get the exit conditions wrong. You'll know when that happens as you'll get an "Out of Stack Space" error message.

(Been there, done that, have the T-shirt )

Xamonas Chegwe

There is an entry in the VB help pages on "Creating recursive procedures". It doesn't add a lot to Loquin's comments though.

ElderKnight

I believe that Loquin's example illustrates the factorial function, not a Fibonacci Series. It is a good example, though!

Edit by loquin: Thanks for pointing that out, Elder Knight. I fixed the post.

Lou wanders off, thinking ... Wow! It wasn't that late when I made that post...

Wim

As Elderknight already said: the example given by Loquin is for calculating the factorial. To calculate the Fibonacci series you have to do:

Xamonas Chegwe

Wim,

I would use Long rather than Integer. With Integer, you will get an overflow error with an input greater than 23. Even Long will throw an error if n > 45. Massive integer methods would be needed to go further - there are a few threads kicking about in this forum on the subject.

Besides, that method is really slow. This is not recursive, but it flies in comparison.


The first few Fibonacci numbers

0
1
1
2
3
5
8
13
21
34
55
89
144
233
377
610
987
1597
2584
4181
6765
10946
17711
28657 *Integer dies here*
46368
75025
121393
196418
317811
514229
832040
1346269
2178309
3524578
5702887
9227465
14930352
24157817
39088169
63245986
102334155
165580141
267914296
433494437
701408733
1134903170
1836311903 *Long dies here*

passel

Yes, I've read elsewhere (wish I knew where), that while Fibonacci and Factorial producing functions are "classic" examples used to demonstrate recursion, they are actually poor examples because cleaner non-recursive methods can be used to produce those series, so aren't a strong argument for the use of recursion.

I don't know the particular article I read. In that one, they gave a simple example where recursion is obviously the best and simplest choice over an iterative solution.
But, since I don't want to do a lot of searching to try and locate that particular article, I'll add yet another page that talks about recursion.

OnErr0r

Solving Towers Of Hanoi is another example where recursion really makes solving much simpler:

http://www.xtremevbtalk.com/showpost...4&postcount=12

passel

Towers of Hanoi. Hey that sounds familiar. Maybe that was the example from the other article. If not, it was something similar to that.

Xamonas Chegwe

Recursive procedures can be fun for producing fractal images such as The Koch Snowflake or the Sierpinski Curve. I wrote loads of similar programs in Logo when I was at college, along with some really complex (not to mention pretty) recursive programs for producing images of fractal trees, ferns, coral, etc.

These days I write commercial mainframe software for the credit industry - which is just as exciting!

loquin

They're used as recursion examples , IMO, only because they're very simple.

Becaues recursion requires that you push variables onto the stack & pop them off on return, they aren't efficient in these examples.

For instance, a non-recursive factorial function would look something like:

Since this function is only called once, the relatively time consuming (and potentially resource consuming) function call only occurrs once. As a result, it should be substancially faster than a recursive factorial function. Whether this would be much of a factor, since the largest value of N for a long is 11 in a factorial calculation, is questionable.