Number of recursions exceeds threshold

Number of call graph cycles over one or more functions is greater than the defined threshold

Since R2024a

Description

A recursion occurs when a function calls itself directly or indirectly. Polyspace^® reports a violation of this rule when the number of such recursions exceed a specified threshold. For details about how Polyspace calculates the number of recursions, see Number of Recursions.

Polyspace uses the default threshold 0, following recommendation from the Hersteller Initiative Software (HIS) standard. To specify a selection file where you can set the threshold, use the option Set checkers by file (-checkers-selection-file) or Checkers activation file (-checkers-activation-file).

When you import comments from previous analyses by using polyspace-comments-import, Polyspace copies any review information on the code metric Number of Recursions in the previous result to this checker in the current result. If the current result contains the same code metric, the review information is copied to the code metric as well.

Risk

Recursion can lead to issues that are difficult to diagnose such as stack overflow. Recursive code is difficult to read and maintain, which could lead to miscalculating the amount of stack required to avoid stack overflow.

Indirect recursions that happen inadvertently are difficult to detect and could lead to stack overflow that is difficult to fix.

Fix

To fix this check, refactor your code to avoid recursion. In many cases, recursive algorithms can be replaced by loops.

Examples

expand all

Avoid Direct Recursion

In this example, the function fibonacci() calculates Fibonacci numbers by using a recursive algorithm. The number of direct recursion is 1, which is higher than the default threshold 0. Polyspace reports a violation of this guideline.

#include <stdio.h>//Noncompliant

#define MAX_N 100
int fibCache[MAX_N];

int fibonacci(int n) {
	if(n <= 1) {
		return n;
	} else {
		// Check if the result is already cached
		if(fibCache[n] != -1) {
			return fibCache[n];
		}

		// Calculate the Fibonacci number and cache the result
		fibCache[n] = fibonacci(n - 1) + fibonacci(n - 2);
		return fibCache[n];
	}
}

Correction — Refactor the Code

One possible correction is to use a loop to replace the recursion.

#include <stdio.h>

#define MAX_N 100
int fibCache[MAX_N];

int fibonacci(int n) {
    if (n <= 1) {
        return n;
    }

    // Check if the result is already cached
    if (fibCache[n] != -1) {
        return fibCache[n];
    }

    // Calculate Fibonacci numbers iteratively and cache the results
    fibCache[0] = 0;
    fibCache[1] = 1;
    for (int i = 2; i <= n; i++) {
        fibCache[i] = fibCache[i - 1] + fibCache[i - 2];
    }

    return fibCache[n];
}

Direct and Indirect Recursion

In this example, the functions validateClosingParentheses() and validateOpeningParentheses() call themselves directly, creating direct recursions. These functions also create an indirect recursion loop: validateClosingParentheses() → validateOpeningParentheses() → validateClosingParentheses(). Polyspace counts three recursions in this code, which exceeds the default threshold 0. Polyspace reports a violation of this rule.

#include <stdio.h> //Noncompliant

int validateClosingParentheses(char* expression, int index);

int validateOpeningParentheses(char* expression, int index) {
    if (expression[index] == '(') {
        return validateClosingParentheses(expression, index + 1);
    } else if (expression[index] == '\0' || expression[index] == ')') {
        return index;
    } else {
        return validateOpeningParentheses(expression, index + 1);
    }
}

int validateClosingParentheses(char* expression, int index) {
    if (expression[index] == ')') {
        return validateOpeningParentheses(expression, index + 1);
    } else if (expression[index] == '\0' || expression[index] == '(') {
        return -1;
    } else {
        return validateClosingParentheses(expression, index + 1);
    }
}

Correction — Refactor the Code

One possible correction is to refactor the code to avoid both direct and indirect recursion.

#include <stdio.h>
#include <stdbool.h>

bool validateParentheses(char* expression) {
    int openCount = 0;

    for (int i = 0; expression[i] != '\0'; i++) {
        if (expression[i] == '(') {
            openCount++;
        } else if (expression[i] == ')') {
            if (openCount == 0) {
                return false;
            }
            openCount--;
        }
    }

    return openCount == 0;
}

Check Information

Group: Software Complexity

Language: C | C++

Acronym: SC20

Default Threshold: 0

Version History

Introduced in R2024a