|
Okay, you are right, my example is one that can be simplified
down to a loop. But isn't most of the recursions can be simplified
down to a loop? So what is the benefit of using recursive algorithm?
Would you kindly make an example for me which the one that can
not be simplified to a loop?
Thanks.
|
|
|
|
|
Alex Ngai wrote:
Would you kindly make an example for me which the one that can
not be simplified to a loop?
Recursive algorithms are best applied to recursive data structures. As Mike has pointed out, manipulating a tree (which is a recursive data structure) is best done using small recursive functions. Other classic recursive algorithms are parsing, solving mazes, the Knight's Tour and the 9-Queens problem. See any classical CS text for descriptions of these.
That being said, remember that every recursive algorithm can be implemented in a non-recursive manner. In fact that's how all recursivs algorithms are executed in machine code! Converting a recursive algorithm to a non-recursive one basically requires you to manually maintain a stack (which is nothing more than a LIFO collection of state).
/ravi
Let's put "civil" back in "civilization"
Home | Articles | Freeware | Music
ravib@ravib.com
|
|
|
|
|
Just because a loop has been eliminated does not make the algorithm more beneficial. All recursive algorithms can be converted to iterative algorithms. There are pros and cons to doing so. Some benefit the programmer, others benefit the computer.
Recursion seems a natural fit when a larger problem can be broken down into one or more smaller problems, using solutions to the smaller problems to solve the original problem. If a few basic rules are followed, recursion is easy (relatively speaking) and practical: 1) Base cases that can be solved without recursion; 2) Making progress towards a base case; 3) Design rule that assumes all recursive calls work; 4) Compound interest rule never duplicates work by solving the same instance of a problem in a separate recursive call.
Consider the recursive implementation of Fibonacci numbers:
long Fib( int N )
{
if (N <= 1)
return 1;
else
return Fib(N - 1) + Fib(N - 2);
}
It seems innocent enough, but for values of N > 30, it's inefficient. Its running time grows exponentially because of all the redundant work (compound interest rule). To compute Fib(N), there is one call to Fib(N - 1) and Fib(N - 2). However, since Fib(N - 1) recursively calls Fib(N - 2) and Fib(N - 3), there are actually two separate calls to Fib(N - 2). Similarly, Fib(N - 3) is computed three times, Fib(N - 4) is computed five times, Fib(N - 5) is computed eight times, etc. These results are thrown away and recomputed later on.
Five birds are sitting on a fence.
Three of them decide to fly off.
How many are left?
|
|
|
|
|
Recursion is easily possible in C and C++, as well as many other languages.
Don't think of it as a "looping is better" / "recursion is better" situation - they are both tools. Certainly there are given procedures that can be expressed using either. But as Mike mentioned, there are some that just seem "natural" to use recursion in implementing, while others make the most sense expressed as loops.
Always remember - you're writing this code for the benefit of the programmer (you and whoever else may read/update the code), not the processor. If it were any other way, you'd be writing machine code...
BTW: you may find this discussion interesting...
Your sincerity about keeping the soapbox organized and civilized is so obvious. I solute your effort.
-- Anonymous, 10/18/03
|
|
|
|
|
Can anyone enlighten me why the compiler is giving this error, "use of class template requires template argument list"?
template<typename T1>
struct MyStruct
{
typedef pair<string, T1<big>&</big>> CLASSINFO;
string className;
static CLASSINFO make_pair <string clsName, const T1<big>&</big> clsRef>
};
typedef int (*PF)(MyStruct<T1><big>&</big> mySt); Thanks for any insight.
William
Fortes in fide et opere!
|
|
|
|
|
|
My property sheet has four pages: new, read, sent, user. When a user is selected, I want to refresh the three pages new, read, and sent. At what event should I handle the refresh?
Eilzabeth
|
|
|
|
|
I'm curious why you'd want to refresh an inactive page. Why not wait until the page is activated before refreshing it?
Five birds are sitting on a fence.
Three of them decide to fly off.
How many are left?
|
|
|
|
|
You are right as I am learning more on using property sheet. The OnSetActive() function will work.
Elizabeth
|
|
|
|
|
Has anyone made a chm file for a Chinese program?
I am having problems getting the Chinese characters to appear in the index. At first I thought it was to with fact that I was generating the HTML with script from an Access database however the characters do appear correctly in other viewers. The Help Topics themselves are also correct if I omit the meta tag specifying the "charset=big5"
Is there different version of the HTML help compiler that I need to use for Asian languages? (I may have the same problem with Japanese and Thai in that case)
Happy programming!!
|
|
|
|
|
Hi,
I have Dialog box which has a edit box. I have a separate thread which waits for a event from another application and updates the edit box.
A part of my codeis given below
UINT ScalerOFC( LPVOID lpParam )
{
......
....
while (TRUE)
{
ScalerOF = RtWaitForMultipleObjects(2,ScalOF,FALSE, INFINITE);
if (ScalerOF==WAIT_OBJECT_0)
{
MessageBeep(MB_ICONHAND);
m_errorlog = ........... // I have the problem here
pDialog->ShowWindow(SW_SHOW);
}
}
return 0;
}
I included a member variable of type CString for the Editbox called m_errorlog, but I couldnt access this variable in my thread.while copiling i get a error saying that m_errorlog is an undeclared identifier.
What should I do to access a member variable from my thread?
Is there any way out?
Thanks,
Deepak Samuel
|
|
|
|
|
Pass the class that you wish the thread to access to the threadproc. If you make the threadproc a static member of your active class then you can access private members.
This kinda thing.
class Active
{
public:
Start()
{
ThreadProc(this);
}
private:
static int WINAPI ThreadProc(LPARAM lParam)
{
Active* impl = reinterpret_cast<Active*>(lParam);
while(true)
{
++impl->m_Member;
}
}
volitile int m_Member;
};
..gads, 2 edits
Ryan
|
|
|
|
|
Hi!
I made a managed web service with VC++ and when I try to get the WSDL I've got this message: 'System.SByte* is inaccessible due to its protection level. Only public types can be processed.'
It seems that some kind of pointers are not allowed to be arguments of web methods (I never worked before with C++ nor Visual Studio .NET and I'm a little... confused?). The question is, how I must replace this data type?
Thanks!!!
Pep Lainez
|
|
|
|
|
How do I declare an array of pointers on the heap?
Rickard Andersson
Here is my card, contact me later!
UIN: 50302279
Sonork: 37318
|
|
|
|
|
int *abc[5]; // is a 5-element array of int pointers
abc[0] = new int;
*abc[0] = 1;
abc[1] = new int;
*abc[1] = 2;
abc[2] = new int;
*abc[2] = 3;
Five birds are sitting on a fence.
Three of them decide to fly off.
How many are left?
|
|
|
|
|
/me
Rickard Andersson
Here is my card, contact me later!
UIN: 50302279
Sonork: 37318
|
|
|
|
|
No wait... I need to create the array at runtime.. that means I can't do as you do.
Rickard Andersson
Here is my card, contact me later!
UIN: 50302279
Sonork: 37318
|
|
|
|
|
int **abc = new int*[5];
abc[0] = new int;
*abc[0] = 1;
abc[1] = new int;
*abc[1] = 2;
abc[2] = new int;
*abc[2] = 3;
Five birds are sitting on a fence.
Three of them decide to fly off.
How many are left?
|
|
|
|
|
Thanks Dave for that. I know I didn't pose the question but I've been beating my head against a wall with that for a few days now not finding anything about it on MSDN. I couldn't figure out where to put the *. Appreciate it.
Always Fear the Man with Nothing to Lose
Jeryth
|
|
|
|
|
use std::vector!
std::vector<CFoo*> v_pFoos;
for(int i=0; i<nVals; i++)
v_pFoos.push_back(new CFoo);
- Nitron
"Those that say a task is impossible shouldn't interrupt the ones who are doing it." - Chinese Proverb
|
|
|
|
|
Hello.
I have a dialog that contains a list control. I have created my own CListCtrl derived class (let's just call it CMyListCtrl). I need to handle the WM_VSCROLL message, but this message is never being received by either my dialog or my list control, but there is a handler for it in both classes. I know I need to subclass my CMyListCtrl list within my dialog but I'm not completely sure how to do this.
I used the class wizard to create a member variable for my list, m_myList, and I set the type of it as being CMyListCtrl.
I have tried a variety of ways to subclass this list control. I have tried both where the list is initialized within my dialog, and also where it is initialized within CMyListCtrl. I have tried using:
m_myList.SubclassDlgItem(IDC_MY_LIST, m_parent);
and
m_myList.SubclassWindow(m_parent->m_hWnd);
both of these will compile and won't give any assertion errors, but the WM_VSCROLL message still isn't being received by my list control (or maybe it's not even being sent in the first place?)
Does anyone have any ideas as to how I can fix this?
Thank you.
|
|
|
|
|
My assumption is that you want to handle the scroll message in the dialog, not the listctrl itself. If you're trying to handle it in your listctrl, then it's a different setup (similar though, as most of the code will go into the listctrl class instead of the dialog). Anything application-specific goes in the dialog handler, and anything control-specific would go in the control handler.
In your dlg's DoDatExchange, you should have something like this
void CMyDlg::DoDataExchange(CDataExchange* pDX)
{
CDialog::DoDataExchange(pDX);
DDX_Control(pDX, IDC_LIST, m_List);
....
}
That is where it is sub-classed. No need to use Subclass* etc.
You should also have this:
BEGIN_MESSAGE_MAP(CMyDlg, CDialog)
ON_WM_VSCROLL()
...
END_MESSAGE_MAP()
This tells the system that this dialog handles the WM_SCROLL message. (this is what you forgot?)
Then, you have this function to actually handle the scroll:
void CMyDlg::OnVScroll(UINT nSBCode, UINT nPos, CScrollBar* pScrollBar)
{
if (*(CSliderCtrl*)pScrollBar == m_List) {
}
CDialog::OnVScroll(nSBCode, nPos, pScrollBar);
}
Hope that fixes things.
You should also have the function declaration in the .h file, of course.
If you're new to MFC, then you might want to use the "Add Windows Message Handler..." wizard (rclick on the dialog in the ClassView). It does all this for you automatically.
The kindest thing you can do for a stupid person, and for the gene pool, is to let him expire of his own dumb choices.
[Roger Wright on stupid people]
We're like private member functions
[John Theal on R&D]
We're figuring out the parent thing as we go though. Kinda like setting up Linux for the first time ya' know...
[Nitron]
|
|
|
|
|
I wanted to handle the message in my listctrl. I have attempted to use the class wizard to create a message map for the WM_VSCROLL message, but that message isn't available for me to use. Then I tried to handle that message in my dialog class, and just make a function call to my listctrl. But that didn't work either. It seems that when the user clicks on the vertical scroll bar within the listctrl (you know the one that is just automatically created when the list gets to be long enough), no WM_VSCROLL message is sent anywhere. If I knew why I wasn't ever getting a WM_VSCROLL message, I'm sure I'd be able to fix this, but I don't know why I'm not getting it.
|
|
|
|
|
i need to create a app similar to command.com or use it fully.
question comes from bellow:
in command.com (dos-window), if execute an app there, the dos-window knows automatically how to communicate with the app - may use pipe, shared memory or socket.
i.e. when i execute java tools via dos-window, if run javac.exe, the pipe is on. if run jdb.exe, socket or shared memory is on.
currently i need to develop a c++ application similar to the dos-window to run those java tools, or take advantage of the dos-window in my app, how to do it?
any hint or light?
thx
includeh10
|
|
|
|
|
We are investigating moving our c++/win32 non-MFC code base to .NET. Is it possible to combine C++ files and c# files in a single solution? or does each solution have to be a single language?
Thank You
|
|
|
|