Programming Opinion

Sooooo... I have a programming 'grade opinion' to ask.

I hate recursion. I don't get it, don't like it, and hate it. If I have to do it, I'll do it.

If say.. I have a pretty good grade in my programming class right now - 94% - and I have this stupid recursion project to do (which I don't get) and I can't get it to DO ANYTHING... so basically, if I don't do it, my grade will drop down to a 81%.

Would you or wouldn't you take this risk of just turning in crap and getting the 0, or actually desperately (and I mean desperate like a person searching for water in a desert) trying to figure out a project (which I don't get)

Btw.. I still have 1 project & final left and I really want a 'B' in the class.

Let me know your opinions!

Why dont you just show us what you've got and ask us for help??

Definitely go for it. Recursion is a very valuable tool when it comes to programming and while the concept may be a bit abstract at first, it'll click eventually.

The way I always think about it is when writing recursive functions, you call that function on the assumption that it does what it should, even though right now it may not.

For example, in implementing the following code:

Code:

---

#include <stdio.h>

int cumulativeSum(int lst[],int size)
{
    if(!size) return 0;
    else      return lst[0]+cumulativeSum(&lst[1],size-1);
}




int main()
{
    int list[5]={1,2,3,4,5};
    printf("%d",cumulativeSum(list,5));
    return 0;
}

---

The code above will output 15, which is the cumulative sum of the list.

Now, you can easily think of the implementation as saying, add the first element to the sum of the rest of the list. cumulativeSum is supposed to return the sum of a list, so if we pass the rest of the list and add that to the first element's value, we'll get the sum of the entire list. So when writing recursive code, just write it under the premise that it works and does what you think it will, and it'll be much easier.

Also, think of recursive functions as having a "base case". This base case is the case on which your recursive function stops. In the code above it stops when the size of the list is 0. Therefore we return what is logically the sum of an empty list (0) and then our recursive function automatically unwinds from there.

Jverkoey,

I understand what recursion is. I can trace-through code, and tell you what it outputs. I just cannot figure out code for myself. btw - I'm the 'recursive word search' post. my recursive word search is my 'doomed project'. Thank you for the encouragement!

Quote:

---

Why dont you just show us what you've got and ask us for help??

---

Because, I would have to post my whole (rather embarassing) code and they I would have a bunch of people yelling at me!

Plus, posting my whole code, in my opinion is cheating. You never learn anything by just posting your whole code, then having someone else debug it for you.

I think these forums are good for asking hints, or providing little bits and parts of code you don't understand/or have a bug. But posting someone's whole entire programming project is just going too far.

Other opinions?

Quote:

---

Originally Posted by tofugirl

I understand what recursion is.

---

Sorry for the misunderstanding.

About your project, sometimes it's good (if time permits) to just try and go at it at a different angle if the current one just plain isn't working. Also, minus the banter in your other post, Quzah did give some good advice on how to implement the code.

Tough it out and get comfortable with recursion, unless you are never going to do anything programming related after this class. Otherwise, you'll suck at writing software.

If you write recursive functions over and over, you'll get how to do it.

If you ask me, the best way to think about recursion when writing a recursive function is to think of it as an embodiment (into computer code) of a mathematical relationship. For example, factorial is defined by

factorial 0 = 1
factorial n = n * factorial (n - 1)

and the recursive way of writing factorial is an embodiment of that. (And in the programming language Haskell, what's written above _is_ the recursive way of writing factorial. Hehe.) For another example, the number of nodes in a binary tree follows the mathematical relationship of

countnodes Null = 0
countnodes node = countnodes (leftchild node) + 1 + countnodes (rightchild node)

This is a simple mathematical relationship, and transcribing it directly into C is straightforward:

Code:

---

struct Tree {
  Tree * left, * right;
  int value;
};

int countnodes(struct Tree * foo) {
  if (foo == NULL)
    return 0;

  return countnodes(foo->left) + 1 + countnodes(foo->right);
}

---

Find a mathematical relationship (maybe 'mathematical' here is the wrong word) that describes your word search function, and then you're essentially done.

Quote:

---

About your project, sometimes it's good (if time permits) to just try and go at it at a different angle if the current one just plain isn't working. Also, minus the banter in your other post, Quzah did give some good advice on how to implement the code.

---

ok ok. I will try to turn in something. I did what Quzah suggested btw. I just have too many bugs.

Maybe I'll go at a 'different angle' as you suggest.. then go at a different angle if that doesn't work, etc.

I'll turn in something that semi-works

I also would never ever use recursion, I have never used it and I started programming in 1982. I suggest that you write the recursion function, as they want it, but also create a function that does the same job without recursion, and then show why that is a better and safer solution. That might give you a plus! I would give you a plus if I was your teacher just for saying that recursion is a bad idea from the beginning!
Good luck! I love that women are learning programming it is needed on this planet!

Quote:

---

Originally Posted by fischerandom

I also would never ever use recursion, I have never used it and I started programming in 1982.

---

I'm almost scared to see the code you've written to traverse the elements of a tree data structure without using recursion.

It reminds me of the Quzah quote in Thantos' sig: "This is like teaching your dog to bark every time you fall asleep. I mean, sure, you could. But is it really a smart thing to do?"

Quote:

---

Originally Posted by cwr

I'm almost scared to see the code you've written to traverse the elements of a tree data structure without using recursion.

It reminds me of the Quzah quote in Thantos' sig: "This is like teaching your dog to bark every time you fall asleep. I mean, sure, you could. But is it really a smart thing to do?"

---

I don't care if you are scared about this fact or not. I am working on a Fischerandom Chess program and I don't use any function recursion calling mechanism to traverse trees in the forest there, nor does the best chess programming gurus, those who wrote the chess programs that are the strongest today like Shredder, Junior and Fritz (or Hydra). Do you know why? Of course you don't. Speed is one of the reasons. There is no reason at all to use a recursive function call mechanism traversing a tree, etc.

The only time I've used recursion in the past 20 years is for transversing file systems -- creating a list of all the files in a directory and all its sub-directories. That's probably impossible to do without recursion. The type of programs I write do not need trees -- just simple one and two dimensional lists of objects.

>Do you know why? Of course you don't. Speed is one of the reasons.
Please don't assume that you know something we don't unless there's sufficient proof. It makes you sound arrogant and jerkish, especially if you're talking to one of the more knowledgeable people on the forum.

>I'm almost scared to see the code you've written to traverse the
>elements of a tree data structure without using recursion.
Actually, unless it's a quick and dirty traversal, I'll take the time to write a good non-recursive iterator based traversal. The code isn't that scary, and it's more powerful and flexible than a recursive traversal by leaps and bounds.

>Because, I would have to post my whole (rather embarassing) code
>and they I would have a bunch of people yelling at me!
Get over it. Nobody cares if you're embarassed, all we care about is helping you. I've only seen a handful of posts that don't offer constructive criticism on any given code in the years that I've been here, so what you construe as people yelling at you is likely no more than them helping you but eschewing the warm and fuzzies that you seem to want. The people that do that are also usually the best programmers here, and rather than worry about being embarrassed or yelled at, post your code, ask what you think are stupid questions, and learn from them. The only stupid question is the one that you don't ask.

I agree with fischerandom, recursion is very rarely a good idea, and we'd probably be better off if we forgot it existed.

I find it ironic that beginners are taught to use recursion while told never to use goto. Recursion is potentially far more dangerous and there are more legitimate uses of goto than recursion.

Quote:

---

Creating a list of all the files in a directory and all its sub-directories. That's probably impossible to do without recursion.

---

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

Quote:

---

I'm almost scared to see the code you've written to traverse the elements of a tree data structure without using recursion.

---

This is a prime example of when recursion is dangerous. Sure it works in testing with a few deep. A few months later, customers start losing data when they get "out of stack space exceptions".

In summary, the benefits of using an explicit loop and stack rather than recursion are:

• Explicit version can fail gracefully, recursion version explodes.
• Explicit version can use as much memory as available. If it needs more, the stack can even be persisted to hard disk. Recursion version can only use up to the reserved stack memory, 1MB by default on Windows machines (similar on 32bit *nix, I think).
• Explicit version is faster.

Quote:

---

Originally Posted by Prelude

>Do you know why? Of course you don't. Speed is one of the reasons.
Please don't assume that you know something we don't unless there's sufficient proof. It makes you sound arrogant and jerkish, especially if you're talking to one of the more knowledgeable people on the forum.

---

Well did you see what cwr wrote to me?
I'm almost scared to see the code you've written to traverse the elements of a tree data structure without using recursion.

It reminds me of the Quzah quote in Thantos' sig: "This is like teaching your dog to bark every time you fall asleep. I mean, sure, you could. But is it really a smart thing to do?"

For this reason I kicked back. 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. And there is also a difference between assuming and knowing. And I know I am right, he just tried to make me look like a fool out of a horses arse and I don't like such things and I don't like jeallous people either. Some people in here are experienced and can help with technical questions to beginners, but all too often I think they do it in a very arrogant and jerkish way and I am certainly not one of them, besides, I am quite good at C programming after having so many years of experience but I am not behaving bad just because of that. I am a very nice person to those people that behave nice to me and others.

Yes, thinking about it, traversing a tree was a bad example.

That said, when speed isn't of paramount importance (it often isn't), and there is some arbitrary limit imposed, recursion will suffice.

It does often result in easier to understand code, which is often more valueable than efficiency. I'm well aware of the disadvantages of recursion that are mentioned above.

Quote:

---

Recursion version can only use up to the reserved stack memory, 1MB by default on Windows machines (similar on 32bit *nix, I think).

---

You are right that this is probably generally the case.

As a matter of interest, Linux will allow the stack to grow just like the heap.

As an experiment I successfully called a recursive function 60 million times on my linux system without it dying. Granted, it was using 1.7GB of memory and went into swap.

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.

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!

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.

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.

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"?

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.

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

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;
}

---