macOS What happens when you invoke main() in another function?

[Muster Mark]

This question came up in another thread without a concrete answer.

Here is an example of what I'm talking about:

#include <stdio.h>
int test (int subject);
int main (void) {
int num;
do{
	printf("Guess a number between 1 and 10 (inclusive)\n");
	scanf("%d",&num);
	}
while(num<1||num>10);
test(num);
return 0;
}

int test (int subject){

if(subject==7)
	printf("Yay!  You guessed it!\n");
else{
	printf("Sorry, try again\n");
	main();
	}
return 0;
}

I realize that invoking main() is unnecessary, because such information can be encoded into the return value. However I was wondering if this method has negative side effects.

Thanks,

--Mark

 

[iSee]

main is just a function. It shouldn't cause any more problems than calling any other function.

 

[lee1210]

It will work, but the problem is that you're using recursion unnecessarily which can lead to huge stack growth. In this program, you only have a few local variables, so it's not so serious. I added a few (very) large arrays to demonstrate the point. Compile this, run it, and guess something between 1 and 10 that isn't 7 a few times and note the result. This is caused by unbounded stack growth. There are languages that allow for tail recursion, in which you can recurse with 0 stack growth, but C isn't one of them (and in this case the recursion isn't as straightforward since there are two functions that call one another reciprocally).

In the other thread I wasn't trying to indicate that this was "wrong", just stylistically unbecoming and unnecessary. As a totally academic interest, though, you can call main. My major problem with this is that no matter where you call it from, there will be stack growth that you most likely won't get back.

-Lee

#include <stdio.h>
int test (int subject);
int main (void) {
int num;
double v[300000];
do{
        printf("Guess a number between 1 and 10 (inclusive)\n");
        scanf("%d",&num);
        }
while(num<1||num>10);
test(num);
return 0;
}

int test (int subject){
double v[300000];

if(subject==7)
        printf("Yay!  You guessed it!\n");
else{
        printf("Sorry, try again\n");
        main();
        }
return 0;
}

 

[ChrisA]

...
I realize that invoking main() is unnecessary, because such information can be encoded into the return value. However I was wondering if this method has negative side effects.

Thanks,

--Mark

In this case the only problem is memory usage will grow with each recursive call.

But in general what happens if you wanted to pass comand line options to main. with something like this

guess -L2 -U55

How would main know not to parse it's argument list.

Also there is a convetion you should follow. Every program needs to return a "return code" back to the shell to indicate sucess or failure. And I think every program should accept a-V option to print it's version number and a -h for help.

In addition you really should check to see if scanf fails.

 

[Sander]

int main(int argc, char *argv[])
{
    return argc < 2 ? 1 : argc*main(argc - 1, NULL);
}

This will return the factorial of the number of arguments you gave your program. Utterly pointless, but isn't it sexy?

P.S. My book doesn't endorse this style, don't worry.

 

[Muster Mark]

Thanks for the replies,

they are most informative.

I have one more question though: if you have a lot of variable declarations in another function that you invoke from main (such as in the example by lee, somthing like 'long long num[3000000];' one would run into the same problem if that function was called many times, right?

Just trying to make sure I understand this properly.

Thanks,
Mark

P.S. I tried your script Lee, and nothing seemed to happen. Should I be looking for something?

 

[lee1210]

they are most informative.

I have one more question though: if you have a lot of variable declarations in another function that you invoke from main (such as in the example by lee, somthing like 'long long num[3000000];' one would run into the same problem if that function was called many times, right?

Just trying to make sure I understand this properly.

Thanks,
Mark

If it was called a lot recursively, yes. If there were a number of functions with a lot of large local variables, any combination of calling them could overwhelm the stack space. But, say, a single function that's called from main, then returns, that has a large stack should be fine, because its local variables will be moved off the stack when the function returns.

If it's calling itself, then yes. My major issue with calling main is that normally when main returns it's because the program is over. Things get murky when you're calling it without the intent for it to return. This is because everything that you've called to that point is still on the stack, but you won't be "popping" those stack frames until the program exits.

-Lee

 

[Muster Mark]

Ok, I think I get it now. As long as a function returns a value, it's ok if it is called many times and has large local variables. If there are large local variables and the function is called many times w/o returning a value, one could run into problems.

If it was called a lot recursively, yes. If there were a number of functions with a lot of large local variables, any combination of calling them could overwhelm the stack space. But, say, a single function that's called from main, then returns, that has a large stack should be fine, because its local variables will be moved off the stack when the function returns.

If it's calling itself, then yes. My major issue with calling main is that normally when main returns it's because the program is over. Things get murky when you're calling it without the intent for it to return. This is because everything that you've called to that point is still on the stack, but you won't be "popping" those stack frames until the program exits.

-Lee

 

[lee1210]

Ok, I think I get it now. As long as a function returns a value, it's ok if it is called many times and has large local variables. If there are large local variables and the function is called many times w/o returning a value, one could run into problems.

Everything is going to have to return eventually, but yes, that's pretty much it. Normally main doesn't return until your program is done, so that's why it was a little more tricky.

You're probably not at the point of dealing with recursion for practical means, but just keep in mind that you want to keep stack variables to a minimum in a function that's to be used recursively, including arguments. My example was extreme so you could see the crash quickly, but if something is going to call itself directly or indirectly, the stack local variables will add up (just more slowly).

Note that this is all C-specific. Languages that support tail-recursion like lisp and haskell can get around this because when you use that specific form of recursion, the stack frame is reused for each call.

-Lee

 

[mobilehaathi]

Note that this is all C-specific. Languages that support tail-recursion like lisp and haskell can get around this because when you use that specific form of recursion, the stack frame is reused for each call.

I swear I've written tail-recursive functions in C before. Granted, it required a "helper" function but....

Do you mean a "regular" recursive function in lisp/haskell automatically reuses the stack frame? If so....cool.

 

[lee1210]

I swear I've written tail-recursive functions in C before. Granted, it required a "helper" function but....

Do you mean a "regular" recursive function in lisp/haskell automatically reuses the stack frame? If so....cool.

I'm not a scholar in this area, but my understanding is that to make C perform tail-recursion whilst avoiding stack growth, one has to use some workarounds. One of them is to have a helper function that makes every function call for you. When your function returns, it would have to return the address of the next function to call and the arguments with which it should be called. Since the original function has returned, its stack frame has been popped, and a new frame is added to make the new call. This is called "trampolining", using the piece of code that does the "call management" for you as a trampoline to jump up into a function,then drop down to the trampoline to be sprung back up.

Here's an article discussing another method of tail-recursion with no stack growth in C:
http://home.pipeline.com/~hbaker1/CheneyMTA.html

You can write functions in C that are tail-recursive without any of these techniques, but you still pay for each stack frame. Another option would be to convert your series of recursive calls to a structure like a while loop, which would operate within the same stack frame.

I haven't needed Haskell on my machine until this point, but HUGS is installing now. I'll post a bit of code when it gets finished. LISP (and LISP-alikes such as scheme) and Haskell essentially require tail call optimization to work well, because the stacks in a functional language would be quickly overwhelmed otherwise.

BTW, the tampoline business above was brought into being in order to implement Scheme using C as an intermediate between Scheme code and machine code.

-Lee

 

[lee1210]

Got HUGS, revived some of my haskell knowledge after not doing tail-recursion properly... and this is what I've got:

deepcall :: [Integer] -> Integer -> Integer
deepcall [] acc = acc
deepcall (x:xs) acc = deepcall xs $! (x + acc)

makedeep :: Integer -> Integer
makedeep n = deepcall [1..n] 0

To sum up n + n-1 + ... + 1, the call would be:
makedeep 12345

For example:
makedeep 1070690
result:
573189073395

In C:

#include <stdio.h>
long int sum(long int);
int main(int argc, char *argv[]) {
  long int x;
  x = sum(200060);
  printf("The value is: %lld\n",x);
}

long int sum(long int input) {
  if(input == 1) return 1;
  return input + sum(input - 1);
}

This is obviously a trivial example, and this could easily be made a loop in C, but the topic was recursion. I couldn't get over about 175000 without this dying. Note that the stack is only the argument passed to sum, which is 8 bytes. There are no other contrived locals as in previous examples.

The stack does not grow in the haskell example, and scheme and lisp compilers should do the same tail call optimization.

I didn't mean to imply that C could not do tail recursion, it just doesn't optimize this by default.

-Lee

 

[mobilehaathi]

Cool, thanks for that! Although my haskell is extremely rusty, so I'll have to remind myself a bit....

Got HUGS, revived some of my haskell knowledge after not doing tail-recursion properly... and this is what I've got:

deepcall :: [Integer] -> Integer -> Integer
deepcall [] acc = acc
deepcall (x:xs) acc = deepcall xs $! (x + acc)

makedeep :: Integer -> Integer
makedeep n = deepcall [1..n] 0

To sum up n + n-1 + ... + 1, the call would be:
makedeep 12345

For example:
makedeep 1070690
result:
573189073395

In C:

#include <stdio.h>
long int sum(long int);
int main(int argc, char *argv[]) {
  long int x;
  x = sum(200060);
  printf("The value is: %lld\n",x);
}

long int sum(long int input) {
  if(input == 1) return 1;
  return input + sum(input - 1);
}

This is obviously a trivial example, and this could easily be made a loop in C, but the topic was recursion. I couldn't get over about 175000 without this dying. Note that the stack is only the argument passed to sum, which is 8 bytes. There are no other contrived locals as in previous examples.

The stack does not grow in the haskell example, and scheme and lisp compilers should do the same tail call optimization.

I didn't mean to imply that C could not do tail recursion, it just doesn't optimize this by default.

-Lee

 

[lee1210]

Cool, thanks for that! Although my haskell is extremely rusty, so I'll have to remind myself a bit....

For reference on $!:
http://haskell.org/onlinereport/basic.html#strict-eval

Lazy evaluation isn't always what you want. In this case we want the sum to be evaluated before each call, otherwise the evaluation of x+acc will be delayed until the result is needed, which causes problems.

The rest of it is pretty straight-forward, but it took me a while to rediscover that while i was writing this.

-Lee