Xtreme Visual Basic Talk

Xtreme Visual Basic Talk (http://www.xtremevbtalk.com/)
-   General (http://www.xtremevbtalk.com/general/)
-   -   calling itself? (http://www.xtremevbtalk.com/general/270968-calling.html)

dan_e6 09-19-2006 05:42 PM

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 ?

Diurnal 09-19-2006 05:54 PM

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 09-19-2006 11:15 PM

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!

DougT 09-20-2006 01:52 AM

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 :D )

Xamonas Chegwe 09-20-2006 04:05 AM

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 09-20-2006 06:20 AM

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

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

Wim 09-20-2006 07:27 AM

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

Xamonas Chegwe 09-20-2006 08:01 AM

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*

passel 09-20-2006 09:28 AM

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 09-20-2006 09:37 AM

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

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

passel 09-20-2006 09:40 AM

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 09-20-2006 09:47 AM

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

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

loquin 09-20-2006 01:58 PM

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.


All times are GMT -6. The time now is 12:40 AM.

Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Search Engine Optimisation provided by DragonByte SEO v2.0.15 (Lite) - vBulletin Mods & Addons Copyright © 2017 DragonByte Technologies Ltd.
All site content is protected by the Digital Millenium Act of 1998. Copyright©2001-2011 MAS Media Inc. and Extreme Visual Basic Forum. All rights reserved.
You may not copy or reproduce any portion of this site without written consent.