Number of Recursions

Количество циклов графика вызовов для одной или нескольких функций

Описание

Метрика предоставляет количественную оценку количества циклов рекурсии в вашем проекте. Метрика является суммой:

Количество прямых рекурсий (самокурсивные функции или функции, вызывающие себя).
Количество сильно связанных компонентов, образованных циклами косвенной рекурсии в вашем проекте. Если вы рассматриваете циклы рекурсии как ориентированный граф, график сильно связан, если существует путь между всеми парами вершин.
Чтобы вычислить количество сильно связанных компонентов:
1. Нарисуйте циклы рекурсии в коде.
  Например, циклы рекурсии в этом примере показаны ниже.
```
volatile int checkStatus;
void func1() {
   if(checkStatus) {
        func2();
   }
   else {
        func3();
   }
}

func2() {
   func1();
}

func3() {
   func1();
}
```
2. Определите количество сильно связанных компонентов, образованных циклами рекурсии.
  В предыдущем примере существует один сильно связанный компонент. Можно переместиться из любой вершины в другую, следуя путям в графике.
  В списке событий под метрикой показан один из циклов рекурсии в сильно связанном компоненте.

Вызовы через указатель на функцию не рассматриваются.

Рекомендуемый верхний предел для этой метрики равен 0. Чтобы избежать возможности превышения доступного пространства стека, не используйте рекурсии в коде. Рекурсии могут иметь тенденцию легко вытеснять пространство стека. См. примеры роста размера стека с рекурсиями, описанными для этого правила CERT-C, которое запрещает рекурсии.

Чтобы обнаружить использование рекурсий, проверяйте на нарушения одного из MISRA C:2012 Rule 17.2, MISRA C^®:: Правило 16.2 2004 года, MISRA C++:2008 Rule 7-5-4 или JSF^® Правило 119. Обратите внимание, что:

Шашки правил сообщают о каждой функции, которая вызывает себя, прямо или косвенно. Даже если несколько функций участвуют в одном цикле рекурсии, каждая функция сообщается индивидуально.
Проверки правил рассматривают только явные вызовы функций. Для образца, в Коды С++, проверяющие правила игнорируют неявные вызовы конструкторов во время создания объекта. Однако при расчете метрики рассматриваются как неявные, так и явные вызовы.

Для обеспечения пределов на метрики:

В Polyspace^® пользовательский интерфейс, см. «Вычисление метрик сложности кода».
В веб-интерфейсе Polyspace Metrics см. «Сравнение метрик с целями качества программного обеспечения».

Примеры

расширить все

Прямая рекурсия

int getVal(void);
int sum(int val) {
    if(val<0)
        return 0;
    else
        return (val + sum(val-1));
}

void main() {
    int count = getVal(), total;
    assert(count > 0 && count <100);
    total = sum(count);
}

В этом примере количество рекурсий равно 1.

Прямая рекурсия является рекурсией, где функция вызывает себя в собственном теле. Для прямых рекурсий количество рекурсий равно количеству рекурсивных функций.

Косвенная рекурсия с одним графиком вызова

volatile int signal;
void operation2(void);

void operation1(void) {
    int stop = signal%2;
    if(!stop)
        operation2();
}

void operation2(void) {
    operation1();
}

void main() {
    operation1();
}

В этом примере количество рекурсий равно единице. Эти две функции operation1 и operation2 участвуют в цикле графика вызовов operation1 → operation2 → operation1.

Косвенная функция является рекурсией, где функция вызывает себя через другие функции. Для косвенных рекурсий количество рекурсий может отличаться от количества рекурсивных функций.

Несколько циклов графика вызова, образующих один сильно соединенный компонент


volatile int checkStatus;
void func1() {
   if(checkStatus) {
        func2();
   }
   else {
        func3();
   }
}

func2() {
   func1();
}

func3() {
   func1();
}

В этом примере существует два цикла графика вызовов:

func1 → func2 → func1
func1 → func3 → func1

Однако циклы образуют один сильно связанный компонент. Можно переместиться из любой вершины в другую, следуя путям в графике. Следовательно, количество рекурсий равно единице.

Косвенная рекурсия с двумя циклами графика вызова

volatile int signal;
void operation1_1();
void operation2_1();

void operation1() {
    int stop = signal%2;
    if(!stop)
        operation1_1();
}


void operation1_1() {
    operation1();
}

void operation2() {
    int stop = signal%2;
    if(!stop)
        operation2_1();
}

void operation2_1() {
    operation2();
}

void main(){
    operation1();
    operation2();
}

В этом примере количество рекурсий составляет два.

Существует два цикла графика вызовов:

operation1 → operation1_1 → operation1
operation2 → operation2_1 → operation2

Циклы графика вызова образуют два сильно связанных компоненты.

Та же функция, вызываемая при прямой и косвенной рекурсии

volatile int signal;
void operation2();

void operation1() {
    int stop = signal%3;
    if(stop==1)
        operation1();
    else if(stop==2)
        operation2();
}

void operation2() {
    operation1();
}

void main() {
    operation1();
}

В этом примере количество рекурсий составляет два:

Сильно связанный компонент, образованный циклом operation1 → operation2 → operation1.
Авторекурсивная функция operation1.

Метрическая информация

Группа: Проект

Акроним: AP_CG_CYCLE

ЕГО Метрика: Да

См. также

Calculate code metrics (-code-metrics) | MISRA C:2012 Rule 17.2

Документация