C/C++アルゴリズム

再帰とcall stack

再帰関数にはbase caseとそこへ近づく処理が必要です。

再帰とcall stackとは？

再帰関数にはbase caseとそこへ近づく処理が必要です。

問題をより小さなinstanceで解きます。

重要なポイント

空、1要素、重複、ソート済み入力をテストします。
正しさと最適化を分けます。
実務ではstandard libraryを優先します。

CとC++のコード例

実行 →

main.c

#include <stdio.h>

unsigned long long factorial(unsigned number) {
    return number < 2 ? 1 : number * factorial(number - 1);
}

int main(void) {
    printf("%llu\n", factorial(6));
}

期待される出力

C++

実行 →

main.cpp

#include <iostream>

constexpr unsigned long long factorial(unsigned number) {
    return number < 2 ? 1 : number * factorial(number - 1);
}

int main() {
    constexpr auto value = factorial(6);
    std::cout << value << '\n';
}

期待される出力

CとC++の比較

Factorialは時間O(n)、stack O(n)です。大入力は検証し、反復版も検討します。

loop、pointer、length、bufferを明示します。

C++

iteratorとalgorithmが操作と格納方法を分離します。

練習課題

両方を実行して変更し、言語ごとの保証を確認します。

各比較を手で追跡します。
重複と極値をテストします。
standard libraryとbenchmarkします。