194 lines
5.8 KiB
Plaintext
194 lines
5.8 KiB
Plaintext
== Why is this an issue?
|
|
|
|
Having an infinite loop or recursion will lead to a program failure or a program never finishing the execution.
|
|
|
|
[source,csharp]
|
|
----
|
|
public int Sum()
|
|
{
|
|
var i = 0;
|
|
var result = 0;
|
|
while (true) // Noncompliant: the program will never stop
|
|
{
|
|
result += i;
|
|
i++;
|
|
}
|
|
return result;
|
|
}
|
|
----
|
|
|
|
This can happen in multiple scenarios.
|
|
|
|
=== Loop statements
|
|
|
|
`while` and `for` loops with no `break` or `return` statements that have exit conditions which are always `false` will be indefinitely executed.
|
|
|
|
=== "goto" statements
|
|
|
|
`goto` statement with nothing that stops it from being executed over and over again will prevent the program from the completion.
|
|
|
|
=== Recursion
|
|
|
|
When a https://en.wikipedia.org/wiki/Recursion_(computer_science)[recursive] method call chain lacks an exit condition,
|
|
the https://en.wikipedia.org/wiki/Call_stack[call stack] will reach its limit and the program will crash due to a https://learn.microsoft.com/en-us/dotnet/api/system.stackoverflowexception[StackOverflowException].
|
|
|
|
[source,csharp]
|
|
----
|
|
int Pow(int num, int exponent)
|
|
{
|
|
return num * Pow(num, exponent - 1); // Noncompliant: no condition under which Pow isn't re-called
|
|
}
|
|
----
|
|
|
|
In this example, `Pow` will keep calling `Pow` with `exponent - 1` forever, until the program crashes with a StackOverflowException.
|
|
|
|
Recursion provides some benefits.
|
|
|
|
* **Simplified code**: recursion can often lead to more concise and elegant code by breaking down complex problems into smaller, more manageable parts.
|
|
* **Improved code readability**: compared to iterative solutions, recursive solutions can be easier to understand and reason about.
|
|
|
|
However, it has disadvantages as well.
|
|
|
|
* **Stack overflow**: Recursive functions can lead to https://learn.microsoft.com/en-us/dotnet/api/system.stackoverflowexception[stack overflow] if the recursion is too deep, potentially causing the program to crash.
|
|
* **Performance overhead**: Recursive function calls can lead to poor performance due to the need to push and pop https://en.citizendium.org/wiki/Stack_frame#:~:text=In%20computer%20science%2C%20a%20stack,only%20exist%20at%20run%2Dtime[stack frames], making them potentially slower than iterative solutions.
|
|
* **Difficulty in debugging**: Debugging recursive code can be challenging, as multiple recursive calls can make it harder to track the flow of execution and identify logical errors.
|
|
* **Space complexity**: Recursive algorithms may require more memory compared to iterative approaches, as each recursive call adds a new frame to the call stack.
|
|
* **Lack of control**: Recursion can sometimes lead to infinite loops or unexpected behavior if not properly implemented or terminated, making it crucial to have proper base cases and exit conditions.
|
|
|
|
== How to fix it
|
|
|
|
The program's logic should incorporate a mechanism to break out of the control flow loop.
|
|
Here are some examples.
|
|
|
|
=== Code examples
|
|
|
|
* Use a loop condition which eventually evaluates to `false`
|
|
|
|
==== Noncompliant code example
|
|
|
|
[source,csharp,diff-id=1,diff-type=noncompliant]
|
|
----
|
|
public int Sum()
|
|
{
|
|
var i = 0;
|
|
var result = 0;
|
|
while (true) // Noncompliant: the program will never stop
|
|
{
|
|
result += i;
|
|
i++;
|
|
}
|
|
return result;
|
|
}
|
|
----
|
|
|
|
==== Compliant solution
|
|
|
|
[source,csharp,diff-id=1,diff-type=compliant]
|
|
----
|
|
public int Sum()
|
|
{
|
|
var i = 0;
|
|
var result = 0;
|
|
while (result < 1000)
|
|
{
|
|
result += i;
|
|
i++;
|
|
}
|
|
return result;
|
|
}
|
|
----
|
|
|
|
* As S907 generally suggests, avoid using `goto` statements. Instead, you can use a loop statement or explicit recursion.
|
|
|
|
==== Noncompliant code example
|
|
|
|
[source,csharp,diff-id=2,diff-type=noncompliant]
|
|
----
|
|
public int Sum()
|
|
{
|
|
var result = 0;
|
|
var i = 0;
|
|
iteration:
|
|
// Noncompliant: program never ends
|
|
result += i;
|
|
i++;
|
|
goto iteration;
|
|
return result;
|
|
}
|
|
----
|
|
|
|
==== Compliant solution
|
|
|
|
[source,csharp,diff-id=2,diff-type=compliant]
|
|
----
|
|
public int Sum()
|
|
{
|
|
var i = 0;
|
|
var result = 0;
|
|
while (result < 1000)
|
|
{
|
|
result += i;
|
|
i++;
|
|
}
|
|
return result;
|
|
}
|
|
----
|
|
|
|
* For a recursion make sure there is a base case when the recursive method is not re-called.
|
|
|
|
==== Noncompliant code example
|
|
[source,csharp,diff-id=3,diff-type=noncompliant]
|
|
----
|
|
int Pow(int num, int exponent)
|
|
{
|
|
return num * Pow(num, exponent - 1); // Noncompliant: no condition under which Pow isn't re-called
|
|
}
|
|
----
|
|
|
|
==== Compliant solution
|
|
[source,csharp,diff-id=3,diff-type=compliant]
|
|
----
|
|
int Pow(int num, int exponent)
|
|
{
|
|
if (exponent > 1) // recursion is now conditional and stoppable
|
|
{
|
|
num = num * Pow(num, exponent - 1);
|
|
}
|
|
return num;
|
|
}
|
|
----
|
|
|
|
== Resources
|
|
|
|
=== Documentation
|
|
|
|
* Microsoft Learn - https://learn.microsoft.com/en-us/dotnet/csharp/language-reference/statements/iteration-statements#the-for-statement[The "for" statement]
|
|
* Microsoft Learn - https://learn.microsoft.com/en-us/dotnet/csharp/language-reference/statements/iteration-statements#the-while-statement[The "while" statement]
|
|
* Microsoft Learn - https://learn.microsoft.com/en-us/dotnet/csharp/language-reference/statements/jump-statements#the-goto-statement[The "goto" statement]
|
|
* Wikipedia https://en.wikipedia.org/wiki/Recursion_(computer_science)[Recursion - wiki]
|
|
* Microsoft Learn - https://learn.microsoft.com/en-us/dotnet/api/system.stackoverflowexception?view=net-7.0[StackOverflowException class]
|
|
* S907 - "goto" statement should not be used
|
|
|
|
=== Articles & blog posts
|
|
|
|
* Edsger Dijkstra - https://www.cs.utexas.edu/users/EWD/transcriptions/EWD02xx/EWD215.html[A Case against the GO TO Statement]
|
|
|
|
ifdef::env-github,rspecator-view[]
|
|
|
|
'''
|
|
== Implementation Specification
|
|
(visible only on this page)
|
|
|
|
=== Message
|
|
|
|
Add a way to break out of this \[[method|property|property accessor]'s recursion|method|property accessor].
|
|
|
|
'''
|
|
== Comments And Links
|
|
(visible only on this page)
|
|
|
|
include::../comments-and-links.adoc[]
|
|
|
|
endif::env-github,rspecator-view[]
|
|
|