Number of direct recursions exceeds threshold

Number of instances of a function calling itself directly is greater than the defined threshold

Since R2024a

Description

A direct recursion occurs when a function calls itself directly. Polyspace^® reports a violation of this rule when the number of such direct recursions exceed a specified threshold. For details about how Polyspace calculates the number of direct recursions, see Number of Direct 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 Direct 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

Direct 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.

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];
}

Check Information

Group: Software Complexity

Language: C | C++

Acronym: SC19

Default Threshold: 0

Version History

Introduced in R2024a