C言語 再帰処理とリンクリスト構造を使った数字のリスト

C言語　リンクリスト構造を使った数字のリスト - Qiita
https://qiita.com/Kchan_01/items/282d413beffc35696ce8
で書いたコードが再帰処理を使って書き換えられると指摘を頂いたので、書き換えてみる。

再帰的な処理は、帰納的に定義されたデータ・セットに対して相性がいいということを身を以て体感できた。

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

typedef struct List List;
struct List
{
    int number;
    List* next;
};

List* addListNotFirst(List* list, List* newList);
List* addList(List* list, int n);
List* displayList(List* list);
void deleteAll(List* list);

int main(void)
{
    List *list;
    list = NULL;
    list = addList(list, 30);
    list = addList(list, 33);
    list = addList(list, 35);
    list = addList(list, 36);
    list = addList(list, 38);
    list = displayList(list);
    deleteAll(list);
    return 0;
}

List* addListNotFirst(List* list, List* newList)
{
    if(list->next == NULL){
        list->next = newList;
    } else {
        addListNotFirst(list->next, newList);
    }
    return list;
}

List* addList(List* list, int n)
{
    List* newList;

    newList = malloc(sizeof(List));
    newList->number = n;
    newList->next = NULL;

    if(list == NULL){
        list = newList;
        return list;
    }
    return addListNotFirst(list, newList);
}

List* displayList(List* list)
{
    if(list != NULL){
        printf("%d\n",list->number);
        displayList(list->next);
    }
    return list;
}

void deleteAll(List* list)
{
    if(list->next != NULL){
        deleteAll(list->next);
    }
    free(list);
}

所感

再帰的な処理は、帰納的に定義されたデータ・セットに対して相性がいい。ということが身を持って理解できた良い経験だった。

最初書き直した時、下記のような書き方をした。
この書き方だと今回は想定されていないが、NULLのリストが渡されたときに危険。

void displayList(List* list)
{
    printf("%d\n",list->number);
    if(list->next != NULL){
        displayList(list->next);
    }
}

なので、下記のようにまずリストがNULLでないか確認するように書くほうが安全。

List* displayList(List* list)
{
    if(list != NULL){
        printf("%d\n",list->number);
        displayList(list->next);
    }
    return list;
}

また、変数を宣言させた書き方もしてしまったが、これだと再帰の良さを活かせていない。再帰は最初に呼び出した段階に戻ってこさせることができるので、一時的に保持させる変数を置かなくてよいところがメリット。

List* addListNotFirst(List* list, List* newList)
{
    List* first = list;
    if(list->next != NULL){
        addListNotFirst(list->next, newList);
    } else {
        list->next = newList;
    }
    return first;
}

下記のように書ける

List* addListNotFirst(List* list, List* newList)
{
    if(list->next == NULL){
        list->next = newList;
    } else {
        addListNotFirst(list->next, newList);
    }
    return list;
}

【振り返り用：first code】再帰処理とリンクリスト構造を使った数字のリスト
https://qiita.com/Kchan_01/private/5981b8f76a4dea09958e