Register FAQ / Rules Forum Spy Search Today's Posts Mark Forums Read
Go Back   MacRumors Forums > Apple Systems and Services > Programming > Mac Programming

Reply
 
Thread Tools Search this Thread Display Modes
Old Sep 11, 2008, 07:59 PM   #1
Muster Mark
macrumors newbie
 
Join Date: Sep 2008
Location: Natick, MA.
What happens when you invoke main() in another function?

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

Here is an example of what I'm talking about:
Code:
#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
Muster Mark is offline   0 Reply With Quote
Old Sep 11, 2008, 08:13 PM   #2
iSee
macrumors 68030
 
iSee's Avatar
 
Join Date: Oct 2004
main is just a function. It shouldn't cause any more problems than calling any other function.
iSee is offline   0 Reply With Quote
Old Sep 11, 2008, 08:26 PM   #3
lee1210
macrumors 68040
 
lee1210's Avatar
 
Join Date: Jan 2005
Location: Dallas, TX
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

Code:
#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;
}
lee1210 is offline   0 Reply With Quote
Old Sep 12, 2008, 12:32 AM   #4
ChrisA
macrumors G4
 
Join Date: Jan 2006
Location: Redondo Beach, California
Quote:
Originally Posted by Muster Mark View Post
...
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
Code:
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.
ChrisA is offline   0 Reply With Quote
Old Sep 12, 2008, 02:34 AM   #5
Sander
macrumors 6502
 
Join Date: Apr 2008
Code:
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.
Sander is offline   0 Reply With Quote
Old Sep 12, 2008, 01:19 PM   #6
Muster Mark
Thread Starter
macrumors newbie
 
Join Date: Sep 2008
Location: Natick, MA.
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?

Last edited by Muster Mark; Sep 12, 2008 at 01:25 PM. Reason: Added post script.
Muster Mark is offline   0 Reply With Quote
Old Sep 12, 2008, 01:25 PM   #7
lee1210
macrumors 68040
 
lee1210's Avatar
 
Join Date: Jan 2005
Location: Dallas, TX
Quote:
Originally Posted by Muster Mark View Post
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
lee1210 is offline   0 Reply With Quote
Old Sep 12, 2008, 01:44 PM   #8
Muster Mark
Thread Starter
macrumors newbie
 
Join Date: Sep 2008
Location: Natick, MA.
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.

Quote:
Originally Posted by lee1210 View Post
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 is offline   0 Reply With Quote
Old Sep 12, 2008, 02:04 PM   #9
lee1210
macrumors 68040
 
lee1210's Avatar
 
Join Date: Jan 2005
Location: Dallas, TX
Quote:
Originally Posted by Muster Mark View Post
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
lee1210 is offline   0 Reply With Quote
Old Sep 12, 2008, 08:00 PM   #10
mobilehaathi
macrumors 68040
 
mobilehaathi's Avatar
 
Join Date: Aug 2008
Location: Bay Area, CA
Quote:
Originally Posted by lee1210 View Post
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.
__________________
The true way is along a rope that is not spanned high in the air, but only just above the ground. It seems intended more to cause stumbling than to be walked along.
mobilehaathi is offline   0 Reply With Quote
Old Sep 12, 2008, 08:45 PM   #11
lee1210
macrumors 68040
 
lee1210's Avatar
 
Join Date: Jan 2005
Location: Dallas, TX
Quote:
Originally Posted by mobilehaathi View Post
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 is offline   0 Reply With Quote
Old Sep 12, 2008, 10:51 PM   #12
lee1210
macrumors 68040
 
lee1210's Avatar
 
Join Date: Jan 2005
Location: Dallas, TX
Got HUGS, revived some of my haskell knowledge after not doing tail-recursion properly... and this is what I've got:
Code:
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:
Code:
#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 is offline   0 Reply With Quote
Old Sep 13, 2008, 08:41 AM   #13
mobilehaathi
macrumors 68040
 
mobilehaathi's Avatar
 
Join Date: Aug 2008
Location: Bay Area, CA
Cool, thanks for that! Although my haskell is extremely rusty, so I'll have to remind myself a bit....

Quote:
Originally Posted by lee1210 View Post
Got HUGS, revived some of my haskell knowledge after not doing tail-recursion properly... and this is what I've got:
Code:
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:
Code:
#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
__________________
The true way is along a rope that is not spanned high in the air, but only just above the ground. It seems intended more to cause stumbling than to be walked along.
mobilehaathi is offline   0 Reply With Quote
Old Sep 13, 2008, 09:42 AM   #14
lee1210
macrumors 68040
 
lee1210's Avatar
 
Join Date: Jan 2005
Location: Dallas, TX
Quote:
Originally Posted by mobilehaathi View Post
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
lee1210 is offline   0 Reply With Quote

Reply
MacRumors Forums > Apple Systems and Services > Programming > Mac Programming

Thread Tools Search this Thread
Search this Thread:

Advanced Search
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump

Similar Threads
thread Thread Starter Forum Replies Last Post
What happens when you leave you whitebook open over a burning candle? eshroom MacBook 3 Jan 12, 2011 09:11 AM
What happens when you change stores in Itunes? Coolmonster245 iPhone 4 Jan 5, 2011 07:37 PM
This is what happens when you leave your phone in the hot car jdczar iPhone 29 Jul 9, 2010 04:23 AM
What happens when you try to download a file in Safari? vivarey iPad 2 Jul 7, 2010 09:00 PM
What happens when you are put in "Time Out" macuser154 Site and Forum Feedback 36 May 4, 2009 11:10 PM


All times are GMT -5. The time now is 05:31 PM.

Mac Rumors | Mac | iPhone | iPhone Game Reviews | iPhone Apps

Mobile Version | Fixed | Fluid | Fluid HD
Copyright 2002-2013, MacRumors.com, LLC