リンクリストを再帰的に扱う

再帰的な扱いって、基底段階？を考えるのも大事だけれども、もうひとつ押さえた方がいいみたいなのでメモ。

typedef struct Node Node;
struct Node {
  int value;
  Node *next;
}

Node *reverse(Node *n){
  if(!n->next){
    return n;
  } 

  Node *nx = n->next;
  n->next = NULL;
  Node *rn = reverse(nx);
  nx->next = n;
  return rn ;
}

再帰使って逆さ順にするコード。こういう基礎的なものは、ちゃんとした所に載っていると思うのですけど、ちらっと検索しただけでは見つからずしばし頭をなやませました。再帰ってどうしてこんなに混乱するのか...。

if(!n){return NULL;}

が基底段階？というやつ。これも大事なんですけど、再帰は押さえておくべき考え方があると思いまして。

それは、「行き」と「帰り」です。

どちらかというと「帰り」が大事。呼ぶ方である「行き」はまだ分かりやすいと思います。n->next として自分で指定してますし。

帰りは分かりにくい。何故かというと、呼び出したスタックの重なりが既に積まれているので、n->next と関係なく存分になにがしかが出来る。これが何かを考えた時に出来そうで出来なさそうで実は実現出来て、出来た後でもしっくり分からない症状の一因なんじゃないかと。

再帰構造というと、返り値を帰り際にごにょごにょして次に渡すってイメージがありましたが、やらずともいい。

行きにゴニョゴニョして、呼び出して、帰りにゴニョゴニョする。

各段階では自由にローカル変数を保持しておける。

上のコードは、n+1 の位置を行きに覚えておいて、基底段階まで行って新たにリンクリストのヘッドとなる最下部を引っ張ってきてこれを最後までそのまま返す。そして覚えておいた n+1 を使って逆向きにリンクを張ってます。最上部の要素の next は、NULL が入ってないといけませんが、それは帰りには出来ないので行きに入れてます。呼んだ後、つまり呼び元への作業は自由...。

ちなみに、return recursive(n->next);という形は、返ってきてすぐ上に飛ぶので、帰りに何もせず基底段階の返り値がそのまま全体の返り値になるというコード。ぱっと見何故か迷うやつ。メモ。