When will infinite loops, and recursive functions with no stop conditions, eventually stop?
I heard a myth saying that infinite loop or a recursive function with no stop condition will stop when "the stack overflows". Is it right?
For example :
void call()
{
call();
}
or
for(;;){;}
Will they really stop when the stack overflows?
Update: If it really stops, can I detect after how many r开发者_如何转开发ecursive calls?
It really depends on the choice of language.
In some languages, your infinite recursive function will halt with a stack overflow based on system- or language-dependent conditions. The reason for this is that many implementations of function call and return allocate new space for each function call, and when space is exhausted the program will fail. However, other languages (Scheme and various gcc optimization levels) will actually have this program run forever because they are smart enough to realize that they can reuse the space for each call.
In some languages, infinite loops will run forever. Your program will just keep on running and never make progress. In other languages, infinite loops are allowed to be optimized away by the compiler. As an example, the C++ standard says that the compiler is allowed to assume that any loop will either terminate or make some globally-visible action, and so if the compiler sees the infinite loop it might just optimize the loop out of existence, so the loop actually does terminate.
In other words, it really depends. There are no hard-and-fast answers to this question.
Hope this helps!
Your first example is a recursive method call - each invocation of call (in most languages and environments) will create a new stack frame, and eventually you'll run out of stack (you'll get a stack overflow condition).
Your second example involves no recursive method invocation - it's just a loop. No stack frames need to be created, and the stack won't overflow.
Give your examples a shot - the first example will cause a stack overflow faster than you may think. The second will make your fans spin really fast, but nothing will happen otherwise until you kill it.
Depends on which language you are using, the loop will end when maximum memory allocated or max execution time is reached. Some languages will detect infinite loop and stop it from running.
p.s. It is not a myth. You can actually try it.
"Update: If it really stops, can I detect after how many recursive calls?"
You most certainly can:
call(int n){
print(n)
call (n+1)
}
Then just call:
call(1)
When the stack overflow occurs, look at the last printed number. This was the number of method calls you had.
Hope this helps!
N.S.
No matter the language, when I create a loop that is potentially infinite, I always build an "emergency exit" into it. I've done this in C#, VB.Net, VBA, JAVA, and just now for the first time in an IBM DB2 SQL function.
Since the concept is valid in any language, I'll present it in pseudocode, as follows:
Begin Procedure
Declare Variable safety_counter As Integer
Begin loop
...
<body of code>
If some_criteria = True Then <-- this is your normal exit
Exit Loop
End If
...
safety_counter = safety_counter + 1
If safety_counter >= 1000 <-- set to any value you wish
Exit Loop <-- this is the emergency exit
End If
End Loop
Some variations are as follows.
If the loop is simple, the two exit criteria might be written in the same If-Then:
If some_criteria = True Then <-- normal exit
Or safety_counter >= 1000 <-- emergency exit
Exit Loop
End If
safety_counter = safety_counter + 1
An error value might be returned like this:
Begin Procedure
Declare Variable result_value As Integer
Declare Variable safety_counter As Integer
Begin loop
...
<body of code>
If some_criteria = True Then <-- this is your normal exit
Set result_value = abc * xyz <-- the value you seek
Exit Loop
End If
...
safety_counter = safety_counter + 1
If safety_counter >= 1000 <-- set to any sufficient value
Set result_value = (-123) <-- indicate "infinite loop error"
Exit Loop <-- this is the emergency exit
End If
End Loop
Return result_value
There are many possible ways to do this, but the key is in safety_counter, and the way of monitoring it to trigger the emergency exit.
加载中,请稍侯......
精彩评论