[C言語] 再帰関数でポインタを活用する方法

#include <stdio.h>
// 配列を逆順に表示する再帰関数
void printReverse(int *arr, int size) {
    if (size <= 0) return; // ベースケース
    printf("%d ", arr[size - 1]); // 現在の要素を表示
    printReverse(arr, size - 1); // 残りの要素を再帰的に処理
}
int main() {
    int array[] = {1, 2, 3, 4, 5};
    int size = sizeof(array) / sizeof(array[0]);
    printReverse(array, size);
    return 0;
}

5 4 3 2 1

#include <stdio.h>
#include <stdlib.h>
// ノードの定義
typedef struct Node {
    int data;
    struct Node *next;
} Node;
// リンクリストを再帰的に探索して表示する関数
void printList(Node *node) {
    if (node == NULL) return; // ベースケース
    printf("%d ", node->data); // 現在のノードのデータを表示
    printList(node->next); // 次のノードを再帰的に処理
}
int main() {
    // ノードの作成
    Node *head = malloc(sizeof(Node));
    head->data = 1;
    head->next = malloc(sizeof(Node));
    head->next->data = 2;
    head->next->next = malloc(sizeof(Node));
    head->next->next->data = 3;
    head->next->next->next = NULL;
    printList(head);
    // メモリの解放
    free(head->next->next);
    free(head->next);
    free(head);
    return 0;
}

1 2 3

#include <stdio.h>
#include <stdlib.h>
// ノードの定義
typedef struct TreeNode {
    int data;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;
// 二分木を中間順(Inorder)でトラバーサルして表示する関数
void inorderTraversal(TreeNode *root) {
    if (root == NULL) return; // ベースケース
    inorderTraversal(root->left); // 左部分木を再帰的に処理
    printf("%d ", root->data); // 現在のノードのデータを表示
    inorderTraversal(root->right); // 右部分木を再帰的に処理
}
int main() {
    // ノードの作成
    TreeNode *root = malloc(sizeof(TreeNode));
    root->data = 2;
    root->left = malloc(sizeof(TreeNode));
    root->left->data = 1;
    root->left->left = NULL;
    root->left->right = NULL;
    root->right = malloc(sizeof(TreeNode));
    root->right->data = 3;
    root->right->left = NULL;
    root->right->right = NULL;
    inorderTraversal(root);
    // メモリの解放
    free(root->right);
    free(root->left);
    free(root);
    return 0;
}

1 2 3

#include <stdio.h>
// 配列の要素を交換する関数
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}
// パーティションを行い、ピボットの位置を返す関数
int partition(int *arr, int low, int high) {
    int pivot = arr[high]; // ピボットを選択
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return i + 1;
}
// クイックソートの再帰関数
void quickSort(int *arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1); // 左部分をソート
        quickSort(arr, pi + 1, high); // 右部分をソート
    }
}
int main() {
    int array[] = {10, 7, 8, 9, 1, 5};
    int size = sizeof(array) / sizeof(array[0]);
    quickSort(array, 0, size - 1);
    for (int i = 0; i < size; i++) {
        printf("%d ", array[i]);
    }
    return 0;
}

1 5 7 8 9 10

#include <stdio.h>
#include <stdlib.h>
// マージ関数
void merge(int *arr, int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;
    int *L = malloc(n1 * sizeof(int));
    int *R = malloc(n2 * sizeof(int));
    for (int i = 0; i < n1; i++)
        L[i] = arr[left + i];
    for (int j = 0; j < n2; j++)
        R[j] = arr[mid + 1 + j];
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
    free(L);
    free(R);
}
// マージソートの再帰関数
void mergeSort(int *arr, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        mergeSort(arr, left, mid); // 左部分をソート
        mergeSort(arr, mid + 1, right); // 右部分をソート
        merge(arr, left, mid, right); // マージ
    }
}
int main() {
    int array[] = {12, 11, 13, 5, 6, 7};
    int size = sizeof(array) / sizeof(array[0]);
    mergeSort(array, 0, size - 1);
    for (int i = 0; i < size; i++) {
        printf("%d ", array[i]);
    }
    return 0;
}

5 6 7 11 12 13

#include <stdio.h>
// ハノイの塔の再帰関数
void hanoi(int n, char from_rod, char to_rod, char aux_rod) {
    if (n == 1) {
        printf("Move disk 1 from rod %c to rod %c\n", from_rod, to_rod);
        return;
    }
    hanoi(n - 1, from_rod, aux_rod, to_rod);
    printf("Move disk %d from rod %c to rod %c\n", n, from_rod, to_rod);
    hanoi(n - 1, aux_rod, to_rod, from_rod);
}
int main() {
    int n = 3; // ディスクの数
    hanoi(n, 'A', 'C', 'B'); // A, B, Cは棒の名前
    return 0;
}

Move disk 1 from rod A to rod C
Move disk 2 from rod A to rod B
Move disk 1 from rod C to rod B
Move disk 3 from rod A to rod C
Move disk 1 from rod B to rod A
Move disk 2 from rod B to rod C
Move disk 1 from rod A to rod C