このページの内容は最新ではありません。最新版の英語を参照するには、ここをクリックします。

再帰の数

1 つ以上の関数に対する呼び出しグラフ サイクルの数

このページをすべて展開する

説明

このメトリクスでは、プロジェクトの再帰サイクル数の定量的な推定値が提供されます。メトリクスは以下の合計です。

  • 直接再帰 (自己再帰関数または互いを呼び出す関数) の数。

  • プロジェクトの間接再帰サイクルによって形成される強連結要素の数。再帰サイクルを有向グラフと見なす場合、頂点のすべてのペア間にパスが存在すると、グラフは強く連結されています。

    強連結要素の数は、次のように計算します。

    1. コードの再帰サイクルを描画します。

      たとえば、次の例の再帰サイクルを以下に示します。

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

func2() {
   func1();
}

func3() {
   func1();
}

    2. 再帰サイクルによって形成される強連結要素の数を特定します。

      前述の例では、強連結要素が 1 つあります。グラフのパスをたどることによって、任意の頂点から別の頂点に移動できます。

      メトリクスの下のイベント リストに、強連結要素の再帰サイクルの 1 つが表示されます。

Polyspace® はこのメトリクスを計算するために、Polyspace によって計算された呼び出し階層とは異なる、構文呼び出し階層を使用します。このメトリクスは構文階層を使用して計算されるため、到達不能な分岐での呼び出しを考慮し、関数ポインターによる呼び出しは考慮しません。

このメトリクスの推奨上限は 0 です。使用可能なスタック領域を超える可能性を回避するには、コード内で再帰を使用しないでください。再帰はスタック領域を簡単に使い果たす傾向があります。再帰を禁止するこの CERT-C ルールに説明されている、再帰によるスタック サイズ増加の例を参照してください。

再帰の使用を検出するには、MISRA C:2012 Rule 17.2、MISRA C™:2004 Rule 16.2、MISRA C++:2008 Rule 7-5-4、JSF® Rule 119、または [再帰の数がしきい値を超えている] のいずれかの違反をチェックします。次の点に注意してください。

  • ルール チェッカーは、それ自体を直接的または間接的に呼び出すそれぞれの関数について報告します。1 つの再帰サイクルに複数の関数が関与している場合でも、それぞれの関数が個別に報告されます。

  • ルール チェッカーは、明示的な関数呼び出しのみを考慮します。たとえば、C++ コードで、ルール チェッカーはオブジェクト作成時のコンストラクターの暗黙的な呼び出しを無視します。ただし、メトリクスの計算では、暗黙的な呼び出しと明示的な呼び出しの両方を考慮します。

メトリクスに制限を適用するには、以下を参照してください。

例

すべて展開する

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();
}

この例では、再帰の数は 1 です。2 つの関数 operation1 と operation2 は、呼び出しグラフ サイクル operation1 → operation2 → operation1 の形で関係しています。

間接的な関数とは、関数が他の関数を介して自身を呼び出す再帰です。間接再帰では、再帰の数は再帰関数の数と異なる可能性があります。


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

func2() {
   func1();
}

func3() {
   func1();
}

この例では、2 つの呼び出しグラフ サイクルがあります。

  • func1 → func2 → func1

  • func1 → func3 → func1

ただし、これらのサイクルは 1 つの強連結要素を形成します。グラフのパスをたどることによって、任意の頂点から別の頂点に移動できます。そのため、再帰の数は 1 です。

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();
}

この例では、再帰の数は 2 です。

呼び出しグラフ サイクルは 2 つあります。

  • operation1 → operation1_1 → operation1

  • operation2 → operation2_1 → operation2

これらの呼び出しグラフ サイクルは 2 つの強連結要素を形成します。

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();
}

この例では、再帰の数は 2 です。

  • サイクル operation1 → operation2 → operation1 によって形成される強連結要素。

  • 自己再帰関数 operation1。

メトリクス情報

グループ: プロジェクト
頭字語: AP_CG_CYCLE
HIS メトリクス:あり

参考

|

トピック