Thread: Programming Opinion

I think it is better then to practice to use iterative solutions untill you master it instead (of using recursive function calls). I'd rather have some one work in my team that writes rock-solid safe and at the same time very efficient code, even if it takes a longer time because it will be worth it in the end with happy customers and a good reputation for the software company - this is the approach the Propellerhead team from Sweden has, etc.They made music programs like Reason, ReBirth, ReCycle, etc. Sure you guys heard of them. Think!

Originally Posted by cwr

I maintain that there are appropriate situations for the use of recursion in both the realms of learning and the real world.

What "situation" would that be? "learning" what? There is other ways to discover how the stack works, by actually reading about it. What do you mean with "the real word"?

Originally Posted by Thantos

Actually I haven't heard of any of the group's you've mentioned. But lets take an example:

Lets say you have a recursive solution that has a cost score (assign a value to time it takes to execute, amount of memory, etc) of say 100 (made up number on a large scale, so 100 would be fairly low cost).
Now lets say you estimate that the iterative solution has a cost score of 95. Is it worth going after the iterative solution?

No there is just one company I mentioned Propellerhead Software http://www.propellerheads.se, and they made those very cool music applications. I am sure they have no place in their code where function recursion is used.

Even if it would be the case that the performance is only 5% faster with iterative recursion than function recursion, I would still never use function recursion because it is inferrior in every single aspect that was mentioned earlier in this thread. However, if you or someone else here present some code that take use of functional recursion (and it is not homework) I can show you, and I feel sure a bounch of other people here also can show you, an iterative solution to that much better performance than just 5% and at the same time is safer to use.

>Well did you see what cwr wrote to me?
Believe it or not, I did.

>And if you read the posts after that you can also see that other,
>obviously more experienced and knowledgeable people, found that what I said was true.
So the people that agree with you are "obviously more experienced and knowledgeable" while those that don't agree with you are (my words) inexperienced amateurs?

>However, if you or someone else here present some code<snip>
You've made some good points. These are arguments against recursion that I would make, but you seem to be ignoring another performance measure: programmer efficiency. Sometimes it's not cost efficient to have a programmer write a non-recursive version of a recursive solution.

Just as a counter-argument, I offer you a similar challenge. Present a function that uses recursion intelligently and a call to that function that is equally intelligent and point out the dangers. The depth of a good recursive function will typically not be that bad, which suggests that you're thinking of something silly like adding or removing a node from a linked list using recursion. The performance hit has been repeatedly displayed to be acceptable in many cases, especially on modern compilers.

As with everything, it's all in how you use it. You can abuse recursion, or your can use it judiciously. There's a world of difference between the two.

Originally Posted by anonytmouse

INothing is impossible without recursion. Recursion is just the lazy and dangerous version of a loop with a stack. See this post for an example.

You are right -- the coding is only slightly more complex but the recursive method runs about twice as fast as the iterative method (see code below).

As for infinite recursion ... that isn't a problem in MS-Windows file system because there is a maximum path size. But as a general rule-of-thumb recursion has that problem.

Code:

#pragma warning(disable:4786)
#include <windows.h>
#include <stdio.h>
#include <time.h>

struct stack
{
	char *path;
	struct stack* next;
};

struct stack* head = NULL;

char* pop()
{
	char* path = head->path;
	struct stack* s = head;
	head = head->next;
	free(s);
	return path;
}

void push(const char* path)
{
	struct stack* node = (struct stack *)malloc(sizeof(struct stack));
	if(node)
	{
		node->next = head;
		node->path = strdup(path);
		head = node;
	}
}


size_t iterative(const char* beginPath, int* nFiles, int* nDirs)
{
	WIN32_FIND_DATA data;
	time_t t1;
	t1 = GetTickCount();
	*nFiles = 0;
	*nDirs = 0;
	push(beginPath);
	while(head != NULL)
	{
		char hpath[_MAX_PATH];
		char* path = pop();
		char flist[_MAX_PATH];
		strcpy(hpath,path);
		strcpy(flist,path);
		strcat(flist,"\\*.*");
		free(path);
		path = NULL;
		HANDLE hFile = FindFirstFile(flist,&data);
		if(hFile != INVALID_HANDLE_VALUE)
		{
			do {
				if(strcmp(data.cFileName,".") != 0 && strcmp(data.cFileName,"..") != 0)
				{
					if( data.dwFileAttributes & FILE_ATTRIBUTE_DIRECTORY)
					{
						strcpy(flist,hpath);
						strcat(flist,"\\");
						strcat(flist,data.cFileName);
						push(flist);
						(*nDirs)++;
					}
					else
					{
						(*nFiles)++;
					}
				}
			} while( FindNextFile(hFile, &data) != 0);
			FindClose(hFile);
		}
	}
	return GetTickCount() - t1;
}

void recursive(const char* beginPath, int* nFiles, int* nDirs)
{
	WIN32_FIND_DATA data;
	char flist[_MAX_PATH];
	strcpy(flist,beginPath);
	strcat(flist,"\\*.*");
	HANDLE hFile = FindFirstFile(flist,&data);
	if(hFile != INVALID_HANDLE_VALUE)
	{
		do {
			if(strcmp(data.cFileName,".") != 0 && strcmp(data.cFileName,"..") != 0)
			{
				if( data.dwFileAttributes & FILE_ATTRIBUTE_DIRECTORY)
				{
					strcpy(flist,beginPath);
					strcat(flist, "\\");
					strcat(flist, data.cFileName);
					(*nDirs)++;
					recursive(flist,nFiles,nDirs);
				}
				else
				{
					(*nFiles)++;
				}
			}
		} while( FindNextFile(hFile, &data) != 0);
		FindClose(hFile);
	}
}


int main()
{
	int nFiles, nDirs;
	time_t t = iterative("c:\\windows", &nFiles, &nDirs);
	printf("time: %u Number of files: %d, Directories: %d\n", t, nFiles, nDirs);
	nFiles = 0;
	nDirs = 0;
	t = GetTickCount();
	recursive("c:\\windows", &nFiles, &nDirs);
	time_t t2 = GetTickCount();
	printf("time: %u Number of files: %d, Directories: %d\n", t2 - t, nFiles, nDirs);

	system("PAUSE");
	return 0;
}