Recursive function crashes.

Ok. I'm pretty new to C (and programming in general). I started 5 months ago. I have this code:

Code:

#include <stdio.h>
#include <stdlib.h>

/* I'm Lazy */
typedef unsigned long int BIG;

BIG Sum(BIG n);

int main(int argc, char *argv[])
{
	BIG n;
	
	if(argc<2) /*check for argument*/
		return(0);
	
	n=atoi(argv[1]); /*convert to an integer*/
	printf("\nAnswer = %d\n",Sum(n));
	return(0);
}

BIG Sum(BIG n)
{
	BIG result; /*final result variable*/
	
	if (n>0)
	{	
		printf("Calling Sum(%d)\n",n);
		result = n+Sum(n-1);
		/* after all Sum() functions are called, they start returning, returning, returning... :-) */
		printf("Sum() is returning. Partial result= %d\n",result);
		return(result);
	}
	else /*indicates the end of calling all the Sum()  functions*/
	{
		printf("\nFinished Calling Sum(). Return 0\n\n" );
		return(0);
	}
}

It will get a number from the user (inputed as an argument) and it will sum all the numbers from 1 to the number. Example: 4 -> 4+3+2+1 = 10.

I entered some printf() functions to understand how recursiveness works, and I'm all set on that part. The only problem is when I put a number like 99,999. The function gets called, and called, and called 'till 34,906 and then the program crashes and exits.

Why does this happen? I mean, I can also do it like this:

Code:

BIG Sum(BIG n)
{
	BIG result;
	for(result=0;n>0;n--)
	{
		result+=n;
	}
	return(result);
}

But why do recursive functions die like that? Thanks a lot.

It's the nature of recursive functions.

When you call a function, it takes up some stack space, because all the local variables of the function have to be stored on the stack. A recursive function often has many instances of itself executing "at the same time" or whatever, and the local variables for every instance of the function all have to be stored separately.

That's one reason recursion is appealing. On the other hand, the stack isn't infinite, and it will eventually overflow.

It should be noted that the stack size can vary from implementation to implementation, and of course according to whatever is already on the stack. If I ran your program on this computer, the function probably wouldn't get called exactly 34,906 times. Likewise, if you added another variable or removed one from your function, it could be executed more often or less often, because each function call would take up more or less stack space.

For a more detailed explanation do some searching.

[edit] http://en.wikipedia.org/wiki/Recursi...rsus_iteration

Another possible reason for choosing an iterative rather than a recursive algorithm is that in today's programming languages, the stack space available to a thread is often much less than the space available in the heap, and recursive algorithms tend to require more stack space than iterative algorithms.

More detail: http://www.thescripts.com/forum/thread213381.html [/edit]

ok so... there is no way to increase this stack space inside the program then?

Also, that leaves me a little bit worried.

The book I'm learning with (C All-in-one Desk Reference for Dummies) shows how to scan directories in the computer by using recursion... does this mean that this program is also limited? How could I scan all directories and subdirectories without using recursion?

Originally Posted by samus250

ok so... there is no way to increase this stack space inside the program then?

You could probably do it with compiler options. There's no standard way to do it, though. What compiler are you using?

Also, that leaves me a little bit worried.

The book I'm learning with (C All-in-one Desk Reference for Dummies) shows how to scan directories in the computer by using recursion... does this mean that this program is also limited?

Well, probably. Anything that uses recursion might stack overflow at some point. However, some optimizing compilers can actually convert recursion into iteration, especially certain types of recursion. I'm under the impression that if you only recur in one place, this has a better chance of happening -- but that's just a guess.

But seriously, you probably shouldn't be worrying about it. Even when you use tons of local variables, you can usually get several thousand function calls in before the stack overflows.

How could I scan all directories and subdirectories without using recursion?

Use iteration. That's the simple answer. Iteration never has stack issues.

The trouble is, some problems that are simple as recursion are extremely thorny as iteration. Again, it depends on the problem. A directory scanner would probably be reasonably simple to implement as iteration. You might need your own stack.

And that brings me to another point. You can always "simulate" recursion with your own stack. I did this for a (naive) flood-fill once. I kept getting stack overflows, but declaring my own stack and popping and pushing data from and to it worked just fine.

Iteration is generally preferable to recursion. Iteration is often faster, since you don't have the overhead of a function call; plus you don't have to worry about stack overflows -- unless you have a lot of really large local variables.

But I wouldn't hesitate to use recursion if the problem works well that way. If you get stack overflows, fine, convert it to iteration. But meanwhile you have simple code that is easy to read and understand and maintain.

[edit] Ah, I see you asked how to scan directories without recursion, not whether it is possible or not.

I would probably use recursion. Having said that, if I had to use iteration, I'd probably go with my own stack, or use something like this FAQ uses (see the POSIX example with opendir() etc): http://faq.cprogramming.com/cgi-bin/...&id=1044780608
[/edit]

Well... I guess that there is always a way to make something work

I am using Bloodshed Dev-C++ (which I think uses MinGW or something like that...)

Just a couple more questions that have gone through my head since I first started programming:

1. One of the first C programs I wanted to do was a program that gave you the factorial value of a number. But... it seems that these variables are kind of limited. If they get too long, they get completely distorted and the computer spits out nonsense. Is there any ways to fix huge calculations? The program can only calculate up to 170! using unsigned doubles, larger than that, it explodes.

2. If I declare too many variables, does the program run out of stack space, or do the variables depend on your computers RAM?

3. Am I wasting my time learning C, or is it really the most powerfull language out there? Is there any other language considered the language of the future, or can I do practically anything in C?

I just want to feel that I'm learning something usefull :-)

Thanks a lot! You are a real help.

Originally Posted by samus250

Well... I guess that there is always a way to make something work

I am using Bloodshed Dev-C++ (which I think uses MinGW or something like that...)

Just a couple more questions that have gone through my head since I first started programming:

1. One of the first C programs I wanted to do was a program that gave you the factorial value of a number. But... it seems that these variables are kind of limited. If they get too long, they get completely distorted and the computer spits out nonsense. Is there any ways to fix huge calculations? The program can only calculate up to 170! using unsigned doubles, larger than that, it explodes.

There are BIG number libraries that handle digits until they're pouring out both ears, not to worry. The interesting part for a young coder is "Can you program your own big number functions?". This is not trivial, but it is satisfying. Hint: base 10 number system. Reverse the numbers, then work them with the operand, from the one's column, the 10's, etc.

2. If I declare too many variables, does the program run out of stack space, or do the variables depend on your computers RAM?

You can run out of stack space. You can also run out of heap space, program space, constant space, depending on your rig's OS and your compiler. The variables may depend on RAM, or on the amount of virtual memory that your program is allocated.

Running out of stack space is a rarity in a program.

3. Am I wasting my time learning C, or is it really the most powerfull language out there? Is there any other language considered the language of the future, or can I do practically anything in C?

C is a medium high level language. Powerful, concise, and easy gets down to low-level work because it corresponds closely with the underlying hardware, and it runs VERY quickly, because of that. Also, it's procedural - you don't have to think up classes and data constructs and methods, for "objects", If you want to "talk on the phone", you just pick up the receiver and start dialing. You don't need to start defining what a phone is, in your program.

OOP is fine, but has a steep learning curve, less re-usability of code than you'd expect, and lots and lots of new ways to go wrong - VERY wrong.

If run-time is not an issue, languages like Python, Java, or Ruby are excellent choices, IMO. You just can't code a chess game with them, because they're like snails compared to C/C++. (or any other computationally intensive game).

I just want to feel that I'm learning something usefull :-)

examples:

1) I have a team fantasy football league, and I want to show some stats, scores, etc., with a program, including downloading data automatically. Python, Java, or Ruby would be my choice, because it's way easier, and the run-time is not an issue. The program only runs twice a week, at most. I will be far more productive in my time, with Python or Ruby, than in C/C++, for this.

2) I have a Radiologist friend. He'd like me to write a program to improve the images he has digitized, for better contrast. Over the years, his department has collected hundreds of thousands of images. I'd definitely use C for this one.

3) I'd like to code a program to manipulate the music I play in ways that I can select, when I press a foot pedal, in near-real time. C to the rescue, here.

Most programming languages were made for a particular purpose. They may have a general use, as well, but each has a real strength. C is system programming. Fortran was mathematics. Cobol was to make me ill, I mean for business. Pascal was for teaching programming, as was BASIC. Smalltalk is great for AI, Java for cross-platform development, and so on.

Whatever project you're working on, you want to choose a language that is strong in that area, and can meet or exceed the requirements of the project.

Recursion is perfect for directory scanning. You should never run into a problem doing that because nobody has directorys 1000+ levels deep. If you did then a lot of things would have difficulty with it because some OS functions only accept up to a certain number of characters, even though they were enlarged in later versions.

"most powerfull language" is a bit vague. However I'd probably rate C++ as more powerful. There is a lot you can do in C++ that you can't do in C, like exceptions, templates, and template-meta-programming. Both of course have Macros which are also very powerful.

I disagree with this comment:

OOP is fine, but has a steep learning curve, less re-usability of code than you'd expect

OOP in itself doesn't really have a steep learning curve, that's just C++.
Also I don't think that there is less reusability than one expects. I think that only comes from poorly writen classes that are only designed to be extensible, and not reusable. If you design properly for reuse then reuse is what you achieve.

Originally Posted by iMalc

Recursion is perfect for directory scanning. You should never run into a problem doing that because nobody has directorys 1000+ levels deep. If you did then a lot of things would have difficulty with it because some OS functions only accept up to a certain number of characters, even though they were enlarged in later versions.

Couldn't you get around the maximum number of characters by changing the current directory as you traverse up and down?

--
As far as samus's question about recursive directory traversal, the stack only needs to store as many frames as the max depth of the directory structure:

Code:

             0                   1 \
       1           2             2  \ Maximum stack space used
    3     4     5     6          3  / 
  7  8   9 10 11 12 13 14        4 /

Originally Posted by oogabooga

Couldn't you get around the maximum number of characters by changing the current directory as you traverse up and down?

That wouldn't change the length limit of the total directory path, for deeper directories. The total path always starts with the drive letter. Anything less is a partial path only, needed to keep your sanity when using the DOS window.

Thanks a lot guys, you really helped. I'll now have to think about making a DIR Scanner that prints all files and their sizes very neatly in a file and the BIG numbers functions. Thanks for the idea Adak!