第30問の答え

答え

int SumListValues(const ListNode *pNode) {
  if (pNode == 0) {
    return 0;
  }

  return pNode->value + SumListValues(pNode->pNext);
}

解説

これは、「再帰呼び出し（recursive call）」に関する出題でした。再帰呼び出しとは、ある関数の処理中で、その関数を再び呼び出す手法のことです。

問題の関数は、次のような形をしていました。

int SumListValues(const ListNode *pNode) {
  ……
}

この関数は、引数pNodeで連結リストのノードを受け取ります。そして、そのノード以降の値の合計を返すというものです。

値の合計を再帰呼び出しで求めるには、次の2つに分けて考えればいいですね。

• pNodeの値（pNode->value）
• pNodeの次のノード（pNode->pNext）以降の値の合計

この2つを足せば、pNode以降の値の合計になるはずです。

int SumListValues(const ListNode *pNode) {
  return pNode->value + SumListValues(pNode->pNext);
}

自分自身を無制限に呼び出し続けようとすれば、いずれプログラムはクラッシュしてしまいます。そのため、再帰呼び出しは「どこでストップするか」が重要です。

今のクラッシュは、ノードが4つしか存在しないのに対し、5回目の呼び出しを行ったために発生したものでした。このとき、引数は0（NULL）になっていたはずです。最後のノードに対するpNode->pNextには、0が格納されているためです。

  ListNode node4 = { 40, 0 }; /* ← 最後のノードのpNextは0（NULL） */
  ListNode node3 = { 30, &node4 };
  ListNode node2 = { 20, &node3 };
  ListNode node1 = { 10, &node2 };

int SumListValues(const ListNode *pNode) {
  if (pNode == 0) {
    /* ここでストップさせたい！ */
  }

  return pNode->value + SumListValues(pNode->pNext);
}

int SumListValues(const ListNode *pNode) {
  if (pNode == 0) {
    return 0;
  }

  return pNode->value + SumListValues(pNode->pNext);
}

今回の題材は、連結リスト構造でした。そのノードは、次のような形をしています。

typedef struct ListNode {
  int value;
  struct ListNode *pNext;
} ListNode;

ノードが一列につながるため、ループで処理できることも多いでしょう。

では、データがツリー構造だった場合はどうでしょうか。例えば、つながりが左右2方向に枝分かれする「二分木（binary tree）」のノードは、次のような形をしています。

typedef struct TreeNode {
  int value;
  struct TreeNode *pLeft;
  struct TreeNode *pRight;
} TreeNode;

ツリー内の値を合計したいと思ったとき、whileループやforループを使うのは無理があります。でも、次のように再帰呼び出しを使えば、プログラムはシンプルになります。

int SumTreeValues(const TreeNode *pNode) {
  if (pNode == 0) {
    return 0;
  }

  return pNode->value + SumTreeValues(pNode->pLeft) + SumTreeValues(pNode->pRight);
}

これは、値の合計を次の3つに分けて考え、足し合わせているのです。

• pNodeの値（pNode->value）
• pNodeの左側のノード（pNode->pLeft）以降の値の合計
• pNodeの右側のノード（pNode->pRight）以降の値の合計

さて。

ここまで読んでいただき、ありがとうございました！C言語にまつわる全30問のクイズ、いかがだったでしょうか？現実の問題解決に役立てられる部分が少しでもあったなら、とても嬉しいです。

本シリーズの問題は、読み物としても楽しんでいただけるよう心がけて制作しました。もし「途中から読んだよ」という場合は、ぜひ「問題一覧」に戻って、ほかの問題にもチャレンジしてみてください！

修正後のプログラム

#include <stdio.h>
#include <stdlib.h>

typedef struct ListNode {
  int value;
  struct ListNode *pNext;
} ListNode;

int SumListValues(const ListNode *pNode) {
  if (pNode == 0) {
    return 0;
  }

  return pNode->value + SumListValues(pNode->pNext);
}

int main(void) {
  ListNode node4 = { 40, 0 };
  ListNode node3 = { 30, &node4 };
  ListNode node2 = { 20, &node3 };
  ListNode node1 = { 10, &node2 };

  printf("Sum: %d\n", SumListValues(&node1));

  return EXIT_SUCCESS;
}

Sum: 100