|
Hello,
It's been a while since I learned about recursion in Java. Can somebody explain exactly how recursion works in C++? (ie. A recursive function call)
Thanks.
|
|
|
|
|
Recursion
A function can call itself. This is called recursion, and recursion can be direct or indirect. It is direct when a function calls itself; it is indirect recursion when a function calls another function that then calls the first function.
Some problems are most easily solved by recursion, usually those in which you act on data and then act in the same way on the result. Both types of recursion, direct and indirect, come in two varieties: those that eventually end and produce an answer, and those that never end and produce a runtime failure. Programmers think that the latter is quite funny (when it happens to someone else).
It is important to note that when a function calls itself, a new copy of that function is run. The local variables in the second version are independent of the local variables in the first, and they cannot affect one another directly, any more than the local variables in main() can affect the local variables in any function it calls, as was illustrated in Listing 5.4.
To illustrate solving a problem using recursion, consider the Fibonacci series:
1,1,2,3,5,8,13,21,34...
Each number, after the second, is the sum of the two numbers before it. A Fibonacci problem might be to determine what the 12th number in the series is.
One way to solve this problem is to examine the series carefully. The first two numbers are 1. Each subsequent number is the sum of the previous two numbers. Thus, the seventh number is the sum of the sixth and fifth numbers. More generally, the nth number is the sum of n - 2 and n - 1, as long as n > 2.
Recursive functions need a stop condition. Something must happen to cause the program to stop recursing, or it will never end. In the Fibonacci series, n < 3 is a stop condition.
The algorithm to use is this:
1. Ask the user for a position in the series.
2. Call the fib() function with that position, passing in the value the user entered.
3. The fib() function examines the argument (n). If n < 3 it returns 1; otherwise, fib() calls itself (recursively) passing in n-2, calls itself again passing in n-1, and returns the sum.
If you call fib(1), it returns 1. If you call fib(2), it returns 1. If you call fib(3), it returns the sum of calling fib(2) and fib(1). Because fib(2) returns 1 and fib(1) returns 1, fib(3) will return 2.
If you call fib(4), it returns the sum of calling fib(3) and fib(2). We've established that fib(3) returns 2 (by calling fib(2) and fib(1)) and that fib(2) returns 1, so fib(4) will sum these numbers and return 3, which is the fourth number in the series.
Taking this one more step, if you call fib(5), it will return the sum of fib(4) and fib(3). We've established that fib(4) returns 3 and fib(3) returns 2, so the sum returned will be 5.
This method is not the most efficient way to solve this problem (in fib(20) the fib() function is called 13,529 times!), but it does work. Be careful: if you feed in too large a number, you'll run out of memory. Every time fib() is called, memory is set aside. When it returns, memory is freed. With recursion, memory continues to be set aside before it is freed, and this system can eat memory very quickly. Listing 5.10 implements the fib() function.
--------------------------------------------------------------------------------
WARNING: When you run Listing 5.10, use a small number (less than 15). Because this uses recursion, it can consume a lot of memory.
--------------------------------------------------------------------------------
Listing 5.10. Demonstrates recursion using the Fibonacci series.
1: // Listing 5.10 - demonstrates recursion
2: // Fibonacci find.
3: // Finds the nth Fibonacci number
4: // Uses this algorithm: Fib(n) = fib(n-1) + fib(n-2)
5: // Stop conditions: n = 2 || n = 1
6:
7: #include <iostream.h>
8:
9: int fib(int n);
10:
11: int main()
12: {
13:
14: int n, answer;
15: cout << "Enter number to find: ";
16: cin >> n;
17:
18: cout << "\n\n";
19:
20: answer = fib(n);
21:
22: cout << answer << " is the " << n << "th Fibonacci number\n";
23: return 0;
24: }
25:
26: int fib (int n)
27: {
28: cout << "Processing fib(" << n << ")... ";
29:
30: if (n < 3 )
31: {
32: cout << "Return 1!\n";
33: return (1);
34: }
35: else
36: {
37: cout << "Call fib(" << n-2 << ") and fib(" << n-1 << ").\n";
38: return( fib(n-2) + fib(n-1));
39: }
40: }
Output: Enter number to find: 5
Processing fib(5)... Call fib(3) and fib(4).
Processing fib(3)... Call fib(1) and fib(2).
Processing fib(1)... Return 1!
Processing fib(2)... Return 1!
Processing fib(4)... Call fib(2) and fib(3).
Processing fib(2)... Return 1!
Processing fib(3)... Call fib(1) and fib(2).
Processing fib(1)... Return 1!
Processing fib(2)... Return 1!
5 is the 5th Fibonacci number
Analysis: The program asks for a number to find on line 15 and assigns that number to target. It then calls fib() with the target. Execution branches to the fib() function, where, on line 28, it prints its argument.
The argument n is tested to see whether it equals 1 or 2 on line 30; if so, fib() returns. Otherwise, it returns the sums of the values returned by calling fib() on n-2 and n-1.
In the example, n is 5 so fib(5) is called from main(). Execution jumps to the fib() function, and n is tested for a value less than 3 on line 30. The test fails, so fib(5) returns the sum of the values returned by fib(3) and fib(4). That is, fib() is called on n-2 (5 - 2 = 3) and n-1 (5 - 1 = 4). fib(4) will return 3 and fib(3) will return 2, so the final answer will be 5.
Because fib(4) passes in an argument that is not less than 3, fib() will be called again, this time with 3 and 2. fib(3) will in turn call fib(2) and fib(1). Finally, the calls to fib(2) and fib(1) will both return 1, because these are the stop conditions.
The output traces these calls and the return values. Compile, link, and run this program, entering first 1, then 2, then 3, building up to 6, and watch the output carefully. Then, just for fun, try the number 20. If you don't run out of memory, it makes quite a show!
Recursion is not used often in C++ programming, but it can be a powerful and elegant tool for certain needs.
--------------------------------------------------------------------------------
NOTE: Recursion is a very tricky part of advanced programming. It is presented here because it can be very useful to understand the fundamentals of how it works, but don't worry too much if you don't fully understand all the details.
--------------------------------------------------------------------------------
|
|
|
|
|
AAMOI, where did you cut that from?
Steve S
(I am not a copyright lawyer)
|
|
|
|
|
it's from C++ in 21 days
is it allowed to copy some parts of the book??
if not, how cares?
|
|
|
|
|
Why don't you just post a link next time?
http://newdata.box.sk/bx/c/htm/ch05.htm#Heading43
"The pointy end goes in the other man." - Antonio Banderas (Zorro, 1998)
|
|
|
|
|
Ok, after HOURS - I'm not going to tell you how many - of trying, I'm looking for help!!
I'm trying to write code to snoop at data in textboxes of an accounting application window for my application to automate some other processes.
From the master application window, I EnumChildWindows with my callback function and find the Dialog Window which contains the controls for the data I want. There are NO other child windows.
I can successfully talk to this window with WM_GetText and WM_GetTextLength and verify the window name.
Next I try to GetNextDlgTabItem ( found_window_handle, 0, 0) and it returns the same window handle I passed to it. If I attempt GetNextDlgTabItem ( found_window_handle, 0, 1) it always returns 0. (just changing previous / next)
I then tried to CHEAT and setup a procedure to use GetDlgItem ( found_window_handle, control_id ) - my cheat is to loop for every number between 0 and 99999999 for the control_id. Surprisingly every attempt returns ZERO.
I was reading about Windows Hooks and it stated sometimes messages can be missed because Windows passes them directly to the control rather than the parent dialog window.
If this is the case, Windows must have a table of controls! How do I access this table?!
IF I had not seen this done, I might have given up, but SnagIT -> Object -> Text capture can not only grab the present value of a dialog text object, but it also returns the programmers name for the object. I've also played with password discovery tools that reviel the value hidden behind a password character "*".
I think the solution is hidden somewhere in messaging the parent dialog window, or in discovering the control table or DLGTEMPLATE at runtime. But, the only starting point I have is the Handle of the Dialog Window itself.
Any suggestions, or better, anyone actually done this?!
|
|
|
|
|
Hi!
I don't know if it helps... but I think had a simmilar Problem.
CWnd * pWnd = FindWindow(0,"some name");
CWnd *pChild1 = pWnd->GetWindow(GW_CHILD);
CWnd *pChild2 = pChild1->GetWindow(GW_HWNDNEXT);
.
.
.
till you find the right window....
I used the Spy++ to check the Dialog for all the windows...
|
|
|
|
|
Hi wb,
I have located the CWnd of the window I want. It's the controls of this window that I can't access.
Do you know, are controls suppose to have window handles too?
GetWindow isn't seeing them. In testing Spy++ doesn't see them either. Someone suggested using EnumChildWindows instead, but it reports the same result.
Jim ô¿ô
|
|
|
|
|
I have a program writen on VC++,and it uses the VC++ graphic libraries,which I don't know.I've managed to understand somethings with the help od the MSDN pages,but there is one thing I can't: The program opens a fullscreen window,and inside it has three frames.I can't manage to edit the size of those three frames,and the top-left and the top-right ones are just a few inches,and the one at the bottom takes almost all the screen.So can you tell me what's the method or variable that controls this size? I'm working on an already writen program,that makes it more difficult...
|
|
|
|
|
No-one can answer this, you're asking us to poke around inside the code that you have, and we don't. What sort of frames, is it a splitter window, or ( as you seem to imply ) are they just drawn to the screen ? What's your OnPaint look like ? What graphics libraries, GDI, GDI+, or something external ?
Christian
I have drunk the cool-aid and found it wan and bitter. - Chris Maunder
|
|
|
|
|
Hi
I tried using Eran Yariv's 2-pass scaling filter (http://www.codeproject.com/bitmap/2_pass_scaling.asp) in my program (Visual C++ 6.0 on Win2k). The program works fine in debug mode, however, when I execute the release version, the scaling's result is not satisfactory, as the scaled images often have many unwanted horizontal green lines on them.
If I changed the preprocessor definition in the project settings to _DEBUG instead of NDEBUG and compile the release version, it works fine, although not the linker gives a warning about msvcrt.dll conflicting with other libraries. Further investigation reveals that the linker now uses msvcrtd.dll instead of msvcrt.dll.
I am curious to know why the program acts so strangely on the release version. Could someone point to me some possible causes for this? Thanks!
|
|
|
|
|
|
Hey guys,
I 'm having problem reading data from a text file.
Sample.dat contains
M
Bob
Dude
56
F
Carmen
Sandiago
33
VP
my code is suppose to read the .DAT file using ios::binary
and feed the information into a class.
example class...
class personInfo
{
char firstname[20];
char lastname[20];
int age;
char gender;
}
class femleInfo : public personInfo
{
char title[5];
}
acutally I have a polymorphic function that reads male info into a maleInfo Class and femaleInfo into a femaleInfo class.
The problem is,how do I read both male and female info seperately and load the appropriate class? (they both have differnt number of data members)....
I tried using seekg function and to move the pointer but I didnt really understand it,
Can someone pls help.
|
|
|
|
|
Create an iostream inserter/extracter for personInfo, have it return the appropriate type of object, based on the first data item read ( the sex ).
Christian
I have drunk the cool-aid and found it wan and bitter. - Chris Maunder
|
|
|
|
|
yes that is what Im doing,
the problem Im having is, how to read the the data into my class ???
I tried myDataFile.read(reinterpret_cast<char*> (&fObject),fObjSize);
and I thought this would copy each data item from the text file into the class varibales???
that doenst seem to be happening, am I missing something?
|
|
|
|
|
Yes, what you need to do is to stream in the variables one at a time. For starters, you've already read the first value out of the file, secondly, you're not allowing for whitespace, which also takes up room in the file. Oh, then you've got byte ordering of any number variable larger than a char, and the fact that that any number is stored not as a number value, but a line of chars.
Christian
I have drunk the cool-aid and found it wan and bitter. - Chris Maunder
|
|
|
|
|
confused .......pls explain a little more.
are you saying that I have to read each varible line by line from the text file and load it onto my class? what function do I use? do I still use
inDataFile.read(reinterpret_cast<char*> ???
what would be the exact lines to use the above ?
thnks for ur help
|
|
|
|
|
Going back to where I started, you need to create an iostream inserter/extracter for the class, like this[^]. Then you'd need to do something like
personStruct a; // whatever your variable type was, it should really be a struct, in any case.
myStream >> a;
// Now check the data member that telss you if it's a female, and treat it accordingly. I'd be incline to use just one struct, and just null the data that is not appropriate, instead of the way you are doing things now.
Christian
I have drunk the cool-aid and found it wan and bitter. - Chris Maunder
|
|
|
|
|
okey got it.
thanks a lot.
|
|
|
|
|
Just curious does anyone have a tutorial on how to make a macro in visual c++. I have this program called total recorder that records streaming audio and i have a radio show that comes on early in the morning. I'm usually not away so i wanted to write a c++ program that would launch total recorder say with shellexecute that part is easy. I just can't figure out how to make it click the mouse like a macro. Thanks for your help.
Talk to me like a baby cause when it comes to programming i still wear a training pants
Win32newb
"Making windows programs worse than they already are"
|
|
|
|
|
You need to look into SendMessage, perhaps. It sounds messy to me though.
I thought you wanted to create a macro in C++, as in #define, I was ready to read you the riot act
Christian
I have drunk the cool-aid and found it wan and bitter. - Chris Maunder
|
|
|
|
|
I think I can help U in it. But definately it needs detailed discussion. Time being. Every Microsoft windows has a class name and window text. and at any given instance Desktop will be parent of all windows. U can find these using Spy++ in windows. So just iterate from desktop as root windows using treeView to Ur target message. Using SendMessage or Postmessage pass WM_BCLICK or WM_LBUTTONDOWN or what ever.
hope it helps
|
|
|
|
|
I looked up SendMessage and post message but wasn't too clear on it.
How do i tell it which window to send it to?
I opened up spy++ and i found my message. I'm assuming i need to the window handle say 004f3c or whatever.
so would i put PostMessage(WM_LBUTTONDOWN,004f3c,NULL);
Sorry but confused i kinda understand what your saying but its new to me so i'm kinda lost.
thanks for the help by the way.
Win32newb
"Making windows programs worse than they already are"
|
|
|
|
|
U can't depend upon handle as they R dynmaic. So derive Windows handle from FindWindow(class name, WinText) kind of API. Use this handle in Ur SendMessage.
Now U must be Pretty clear I think. Mind U there is no standard method of doing this. I derived this method after 2 months of shuffling with Charles Perzolt book. Highly recommended.
One more just read the query posted by codeCharmer "Enumerating Dialog Controls". U have to adopt almost similar Algo.
cheers
Siddharth
|
|
|
|
|
please tell me how can i initialize ITBasicCallControl
interface of tapi3lib.dll in VC.net
thanx....
babur
|
|
|
|
|