calling itself?
calling itself?
calling itself?
calling itself?
calling itself?
calling itself? calling itself? calling itself? calling itself? calling itself? calling itself? calling itself? calling itself?
calling itself? calling itself?
calling itself?
Go Back  Xtreme Visual Basic Talk > > > calling itself?


Reply
 
Thread Tools Display Modes
  #1  
Old 09-19-2006, 05:42 PM
dan_e6's Avatar
dan_e6 dan_e6 is offline
Contributor
 
Join Date: Mar 2004
Posts: 552
Default calling itself?


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 ?
Reply With Quote
  #2  
Old 09-19-2006, 05:54 PM
Diurnalcalling itself? Diurnal is offline
Enthusiast

Retired Leader
* Expert *
 
Join Date: Apr 2002
Location: Bellevue, WA.
Posts: 3,233
Default

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.
Reply With Quote
  #3  
Old 09-19-2006, 11:15 PM
loquin's Avatar
loquincalling itself? loquin is offline
Google Hound

Retired Moderator
* Guru *
 
Join Date: Nov 2001
Location: Arizona, USA
Posts: 12,399
Default

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 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!
__________________
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; 09-20-2006 at 10:15 AM.
Reply With Quote
  #4  
Old 09-20-2006, 01:52 AM
DougT's Avatar
DougT DougT is offline
Ultimate Antique

Administrator
* Expert *
 
Join Date: Sep 2005
Location: Maldon,Essex, UK
Posts: 3,939
Default

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 )
__________________
semel insanivimus omnes
S Data in context = Information, S Information in context = Knowledge, S Knowledge in context = Experience
S Experience in context = Wisdom= Data
Reply With Quote
  #5  
Old 09-20-2006, 04:05 AM
Xamonas Chegwe's Avatar
Xamonas Chegwe Xamonas Chegwe is offline
Junior Contributor
 
Join Date: Jun 2006
Posts: 228
Default

There is an entry in the VB help pages on "Creating recursive procedures". It doesn't add a lot to Loquin's comments though.
Reply With Quote
  #6  
Old 09-20-2006, 06:20 AM
ElderKnightcalling itself? ElderKnight is offline
Senior Contributor

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

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; 09-20-2006 at 10:19 AM.
Reply With Quote
  #7  
Old 09-20-2006, 07:27 AM
Wim's Avatar
Wim Wim is offline
Newcomer
 
Join Date: Aug 2006
Location: Belgium
Posts: 15
Default

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
Reply With Quote
  #8  
Old 09-20-2006, 08:01 AM
Xamonas Chegwe's Avatar
Xamonas Chegwe Xamonas Chegwe is offline
Junior Contributor
 
Join Date: Jun 2006
Posts: 228
Default

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*
Reply With Quote
  #9  
Old 09-20-2006, 09:28 AM
passel's Avatar
passelcalling itself? passel is offline
Sinecure Expert

Super Moderator
* Guru *
 
Join Date: Jun 2003
Location: Upstate New York, usa
Posts: 8,015
Default

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.
__________________
There Is An Island Of Opportunity In The Middle of Every Difficulty.
Miss That, Though, And You're Pretty Much Doomed.
Reply With Quote
  #10  
Old 09-20-2006, 09:37 AM
OnErr0r's Avatar
OnErr0rcalling itself? OnErr0r is offline
Obsessive OPtimizer

Administrator
* Guru *
 
Join Date: Jun 2002
Location: Debug Window
Posts: 13,767
Default

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

http://www.xtremevbtalk.com/showpost...4&postcount=12
__________________
Quis custodiet ipsos custodues.
Reply With Quote
  #11  
Old 09-20-2006, 09:40 AM
passel's Avatar
passelcalling itself? passel is offline
Sinecure Expert

Super Moderator
* Guru *
 
Join Date: Jun 2003
Location: Upstate New York, usa
Posts: 8,015
Default

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.
Reply With Quote
  #12  
Old 09-20-2006, 09:47 AM
Xamonas Chegwe's Avatar
Xamonas Chegwe Xamonas Chegwe is offline
Junior Contributor
 
Join Date: Jun 2006
Posts: 228
Default

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!
Reply With Quote
  #13  
Old 09-20-2006, 01:58 PM
loquin's Avatar
loquincalling itself? loquin is offline
Google Hound

Retired Moderator
* Guru *
 
Join Date: Nov 2001
Location: Arizona, USA
Posts: 12,399
Default

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 non-recursive 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 non-recursive 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; 01-23-2007 at 11:15 AM.
Reply With Quote
Reply


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

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off

Forum Jump

Advertisement:





Free Publications
The ASP.NET 2.0 Anthology
101 Essential Tips, Tricks & Hacks - Free 156 Page Preview. Learn the most practical features and best approaches for ASP.NET.
subscribe
Programmers Heaven C# School Book -Free 338 Page eBook
The Programmers Heaven C# School book covers the .NET framework and the C# language.
subscribe
Build Your Own ASP.NET 3.5 Web Site Using C# & VB, 3rd Edition - Free 219 Page Preview!
This comprehensive step-by-step guide will help get your database-driven ASP.NET web site up and running in no time..
subscribe
calling itself?
calling itself?
calling itself? calling itself?
calling itself?
calling itself?
calling itself? calling itself? calling itself? calling itself? calling itself? calling itself? calling itself?
calling itself?
calling itself?
 
calling itself?
calling itself?
 
-->