Programming Opinion

This is a discussion on Programming Opinion within the C Programming forums, part of the General Programming Boards category; I've noticed the following pattern when people are learning recursion: Fear and loathing because they don't underestand it -> click! ...

  1. #16
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    I've noticed the following pattern when people are learning recursion:

    Fear and loathing because they don't underestand it -> click! I get recursion -> overuse of recursion -> understanding the costs of recursion -> less use of recursion

    Now I will say this: Any programmer that refuses outright to even consider using a tool isn't one I want on my team. Yes its true that for every recursive solution there is an itertive solution that will be less costly at runtime. However for some very complex problems the cost of developing the itertive solution outweighs the benefits at runtime. Thus anyone who can't or won't look to see if its really worth it is not someone I want.

    Now onto another issue: Please stop getting butt hurt over other people's comments. Bickering and e-penis waving is just annoying.

  2. #17
    Registered User fischerandom's Avatar
    Join Date
    Aug 2005
    Location
    Stockholm
    Posts
    71
    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!
    Bobby Fischer Live Radio Interviews http://home.att.ne.jp/moon/fischer/

  3. #18
    cwr
    cwr is offline
    Registered Luser cwr's Avatar
    Join Date
    Jul 2005
    Location
    Sydney, Australia
    Posts
    869
    I totally agree that if you do not know the size limit of your data, or need efficiency, then iterative solutions are definitely the answer.

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

    I apologise for my original rude sounding reply, I just took exception to the blanket implication that recursion should never be used.

  4. #19
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    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?

    And you can have some rock solid recursive code.

    Quote Originally Posted by fischerandom
    Think!
    I ask you to do the same. Think before just defending your position. Ask yourself why, why do you hold that position and why do you feel the need to defend it.

  5. #20
    Registered User fischerandom's Avatar
    Join Date
    Aug 2005
    Location
    Stockholm
    Posts
    71
    Quote 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"?
    Bobby Fischer Live Radio Interviews http://home.att.ne.jp/moon/fischer/

  6. #21
    Registered User fischerandom's Avatar
    Join Date
    Aug 2005
    Location
    Stockholm
    Posts
    71
    Quote 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.
    Bobby Fischer Live Radio Interviews http://home.att.ne.jp/moon/fischer/

  7. #22
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >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.
    My best code is written with the delete key.

  8. #23
    Registered User
    Join Date
    Aug 2005
    Posts
    1,267
    Quote 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;
    }
    Last edited by Ancient Dragon; 11-25-2005 at 09:23 AM.

Page 2 of 2 FirstFirst 12
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 6
    Last Post: 02-27-2009, 04:43 PM
  2. Her opinion, your opinion
    By RoD in forum C++ Programming
    Replies: 4
    Last Post: 12-22-2002, 10:50 AM
  3. Freedom of opinion
    By Shiro in forum A Brief History of Cprogramming.com
    Replies: 1
    Last Post: 02-10-2002, 07:06 AM
  4. opinion about books
    By clement in forum C Programming
    Replies: 7
    Last Post: 09-24-2001, 05:18 PM
  5. your opinion please
    By iain in forum A Brief History of Cprogramming.com
    Replies: 3
    Last Post: 09-10-2001, 06:36 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21