
09192006, 06:42 PM


Contributor


Join Date: Mar 2004
Posts: 552


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


09192006, 06:54 PM

Enthusiast
Retired Leader * Expert *


Join Date: Apr 2002
Location: Bellevue, WA.
Posts: 3,233


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.

__________________
Marty
Try searching for an answer first.
Tag your code [vb][/vb] and be patient... everyone here is a volunteer.

09202006, 12:15 AM


Google Hound
Retired Moderator * Guru *


Join Date: Nov 2001
Location: Arizona, USA
Posts: 12,400


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
Code:
Function Factorial (N as Long) as Long
If N < 0 then
Factorial = 0 ' actually, it's undefined...
ElseIf N <= 1 then
Factorial = 1 ' Exit for the function
Else
Factorial = N * Factorial(N 1) ' Here the function calls itself...
End If
End Function
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 nonrecursively 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 midpoint 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 maxmin = 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!

__________________
Lou
"I have my standards. They may be low, but I have them!" ~ Bette Middler
"It's a book about a Spanish guy called Manual. You should read it." ~ Dilbert
"To understand recursion, you must first understand recursion." ~ unknown
Last edited by loquin; 09202006 at 11:15 AM.

09202006, 02:52 AM


Ultimate Antique
Administrator * Expert *


Join Date: Sep 2005
Location: Maldon,Essex, UK
Posts: 3,939


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 Tshirt )

__________________
semel insanivimus omnes
S Data in context = Information, S Information in context = Knowledge, S Knowledge in context = Experience
S Experience in context = Wisdom= Data

09202006, 05:05 AM


Junior Contributor


Join Date: Jun 2006
Posts: 228


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


09202006, 07:20 AM

Senior Contributor
Forum Leader


Join Date: Oct 2003
Location: Central Florida
Posts: 1,275


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...

__________________
 D.J.
I do not endorse any items advertised within this frame, and regret that the viewer is subjected to such.
Last edited by loquin; 09202006 at 11:19 AM.

09202006, 08:27 AM


Newcomer


Join Date: Aug 2006
Location: Belgium
Posts: 15


As Elderknight already said: the example given by Loquin is for calculating the factorial. To calculate the Fibonacci series you have to do:
Code:
Private Function Fib(n As Integer) As Integer
Select Case n
Case Is = 0
Fib = 0
Case Is = 1
Fib = 1
Case Is > 1
Fib = Fib(n  1) + Fib(n  2)
End Select
End Function


09202006, 09:01 AM


Junior Contributor


Join Date: Jun 2006
Posts: 228


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.
Code:
Function fib(i As Long) As Long
Dim seed1 As Long, seed2 As Long, sum As Long, count As Long
Select Case i
Case 0
fib = 0
Case Else
seed1 = 0
seed2 = 1
For count = 1 To i
sum = seed1 + seed2
seed1 = seed2
seed2 = sum
Next count
fib = sum
End Select
End Function
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*


09202006, 10:28 AM


Sinecure Expert
Super Moderator * Guru *


Join Date: Jun 2003
Location: Upstate New York, usa
Posts: 8,026


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 nonrecursive 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.

__________________
There Is An Island Of Opportunity In The Middle of Every Difficulty.
Miss That, Though, And You're Pretty Much Doomed.

09202006, 10:37 AM


Obsessive OPtimizer
Administrator * Guru *


Join Date: Jun 2002
Location: Debug Window
Posts: 13,774


__________________
Quis custodiet ipsos custodues.

09202006, 10:40 AM


Sinecure Expert
Super Moderator * Guru *


Join Date: Jun 2003
Location: Upstate New York, usa
Posts: 8,026


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

__________________
There Is An Island Of Opportunity In The Middle of Every Difficulty.
Miss That, Though, And You're Pretty Much Doomed.

09202006, 10:47 AM


Junior Contributor


Join Date: Jun 2006
Posts: 228


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!


09202006, 02:58 PM


Google Hound
Retired Moderator * Guru *


Join Date: Nov 2001
Location: Arizona, USA
Posts: 12,400


Quote:
Originally Posted by 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 nonrecursive methods can be used to produce those series, so aren't a strong argument for the use of recursion.

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 nonrecursive factorial function would look something like:
Code:
Function Fact2 (NFact as Long) as Long
Dim N as Integer
Dim lngTemp as Long
LngTemp = 1
If NFact = 0 or NFact = 1 then Fact2 = 1 else
For N = 2 to NFact
lngTemp = lngTemp * N
Next N
End if
Fact2 = lngTemp
end Function
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.

__________________
Lou
"I have my standards. They may be low, but I have them!" ~ Bette Middler
"It's a book about a Spanish guy called Manual. You should read it." ~ Dilbert
"To understand recursion, you must first understand recursion." ~ unknown
Last edited by loquin; 01232007 at 12:15 PM.

Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)


Thread Tools 

Display Modes 
Linear Mode

Posting Rules

You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts
HTML code is Off





