Skip to content

Latest commit

 

History

History
1804 lines (1375 loc) · 45.6 KB

008-loop.md

File metadata and controls

1804 lines (1375 loc) · 45.6 KB
Raw

ループ

さて、ここまでで変数や関数、標準入出力といったプログラミングの基礎的な概念を教えてきた。あと1つでプログラミングに必要な基礎的な概念はすべて説明し終わる。ループだ。

これまでのおさらい

C++では、プログラムは書いた順番に実行される。これを逐次実行という。

int main()
{
    std::cout << 1 ;
    std::cout << 2 ;
    std::cout << 3 ;
}

実行結果、

123

この実行結果が"123"以外の結果になることはない。C++ではプログラムは書かれた順番に実行されるからだ。

条件分岐は、プログラムの実行を条件付きで行うことができる。

int main()
{
    std::cout << 1 ;

    if ( false )
        std::cout << 2 ;

    std::cout << 3 ;

    if ( true )
        std::cout << 4 ;
    else
        std::cout << 5 ;
}

実行結果、

134

条件分岐によって、プログラムの一部を実行しないということが可能になる。

goto文

ここでは繰り返し(ループ)の基礎的な仕組みを理解するために、最も原始的で最も使いづらい繰り返しの機能であるgoto文を学ぶ。goto文で実用的な繰り返し処理をするのは面倒だが、恐れることはない。より簡単な方法もすぐに説明するからだ。なぜ本書でgoto文を先に教えるかというと、あらゆる繰り返しは、けっきょくのところif文とgoto文へのシンタックスシュガーにすぎないからだ。goto文を学ぶことにより、繰り返しを恐れることなく使う本物のプログラマーになれる。

無限ループ

"hello\n"と3回出力するプログラムはどうやって書くのだろうか。"hello\n"を1回出力するプログラムの書き方はすでにわかっているので、同じ文を3回書けばよい。

// 1回"hello\n"を出力する関数
void hello()
{
    std::cout << "hello\n"s ;
}

int main()
{
    hello() ;
    hello() ;
    hello() ;
}

10回出力する場合はどうするのだろう。10回書けばよい。コードは省略する。

では100回出力する場合はどうするのだろう。100回書くのだろうか。100回も同じコードを書くのはとても面倒だ。読者がVimのような優秀なテキストエディターを使っていない限り100回も同じコードを間違えずに書くことは不可能だろう。Vimならば1回書いたあとにノーマルモードで"100."するだけで100回書ける。

実際のところ、100回だろうが、1000回だろうが、あらかじめ回数がコンパイル時に決まっているのであれば、その回数だけ同じ処理を書くことで実現可能だ。

しかし、プログラムを外部から強制的に停止させるまで、無限に出力し続けるプログラムはどう書けばいいのだろうか。そういった停止しないプログラムを外部から強制的に停止させるにはCtrl-Cを使う。

以下はそのようなプログラムの実行例だ。

$ make run
hello
hello
hello
hello
...
[Ctrl-Cを押す]

goto文は指定したラベルに実行を移す機能だ。

ラベル名 : 文

goto ラベル名 ;
int main()
{
    std::cout << 1 ;

    // ラベルskipまで飛ぶ
    goto skip ;

    std::cout << 2 ;

// ラベルskip
skip :
    std::cout << 3 ;
}

これを実行すると以下のようになる。

13

2を出力すべき文の実行が飛ばされていることがわかる。

これだけだと"if (false)"と同じように見えるが、goto文はソースコードの上に飛ぶこともできるのだ。

void hello()
{
    std::cout << "hello\n"s ;
}
int main()
{
loop :
    hello() ;
    goto loop ; 
}

これは"hello\n"を無限に出力するプログラムだ。

このプログラムを実行すると、

  1. 関数helloが呼ばれる
  2. goto文でラベルloopまで飛ぶ
  3. 1.に戻る

という処理を行う。

終了条件付きループ

ひたすら同じ文字列を出力し続けるだけのプログラムというのも味気ない。もっと面白くてためになるプログラムを作ろう。例えば、ユーザーから入力された数値を合計し続けるプログラムはどうだろう。

いまから作るプログラムを実行すると以下のようになる。

$ make run
> 10
10
> 5
15
> 999
1014
> -234
780

このプログラムは、

  1. "\>"と表示してユーザーから整数値を入力
  2. これまでの入力との合計値を出力
  3. 1.に戻る

という動作を繰り返す。先ほど学んだ無限ループと同じだ。

さっそく作っていこう。

int input()
{
    std::cout << ">"s ;
    int x {} ;
    std::cin >> x ;
    return x ;
}

int main()
{
    int sum = 0 ;
loop :
    sum = sum + input() ;
    std::cout << sum << "\n"s ;
    goto loop ;
}

関数inputは"\>"を表示してユーザーからの入力を得て戻り値として返すだけの関数だ。

"sum = sum + input()"は、変数sumに新しい値を代入するもので、その代入する値というのは、代入する前の変数sumの値と関数inputの戻り値を足した値だ。

このような変数xに何らかの値nを足した結果を元の変数xに代入するという処理はとても多く使われるので、C++では"x = x + n"を意味する省略記法"x += n"がある。

int main()
{
    int x = 1 ;
    int n = 5 ;

    x = x + n ; // 6
    x += n ; // 11
}

さて、本題に戻ろう。上のプログラムは動く。しかし、プログラムを停止するにはCtrl-Cを押すしかない。できればプログラム自ら終了してもらいたいものだ。

そこで、ユーザーが0を入力したときはプログラムを終了するようにしよう。

int input()
{
    std::cout << ">"s ;
    int x {} ;
    std::cin >> x ;
    return x ;
}

int main()
{
    int sum = 0 ;
loop :
    // 一度入力を変数に代入
    int x = input() ;
    // 変数xが0でない場合
    if ( x != 0 )
    {// 実行
        sum = sum + x ;
        std::cout << sum << "\n"s ;
        goto loop ;
    }
    // x == 0の場合、ここに実行が移る
    // main関数の最後なのでプログラムが終了
}

うまくいった。このループは、ユーザーが0を入力した場合に繰り返しを終了する、条件付きのループだ。

インデックスループ

最後に紹介するループは、インデックスループだ。$n$回"hello\n"sを出力するプログラムを書こう。問題は、この$n$はコンパイル時には与えられず、実行時にユーザーからの入力で与えられる。

// n回出力する関数の宣言
void hello_n( int n ) ;

int main()
{
    // ユーザーからの入力
    int n {} ;
    std::cin >> n ;
    // n回出力
    hello_n( n ) ;
}

このコードをコンパイルしようとするとエラーになる。これは実はコンパイルエラーではなくてリンクエラーという種類のエラーだ。その理由は、関数hello_nに対する関数の定義が存在しないからだ。

関数というのは宣言と定義に分かれている。

// 関数の宣言
void f( ) ;

// 宣言
void f( )
// 定義
{ }

関数の宣言というのは何度書いても大丈夫だ。

// 宣言
int f( int x ) ;

// 再宣言
int f( int x ) ;

// 再宣言
int f( int x ) ;

関数の宣言というのは戻り値の型や関数名や引数リストだけで、";"で終わる。

関数の定義とは、関数の宣言のあとの"{}"だ。この場合、宣言のあとに";"は書かない。

int f( int x ) { return x ; }

関数の定義は一度しか書けない。

// 定義
void f() {}
// エラー、再定義
void f() {}

なぜ関数は宣言と定義とに分かれているかというと、C++では名前は宣言しないと使えないためだ。

int main()
{
    // エラー
    // 名前fは宣言されていない
    f() ;
}

// 定義
void f() { }

なので、必ず名前は使う前に宣言しなければならない。

// 名前fの宣言
void f() ;

int main()
{
    // OK、名前fは関数
    f() ;
}

// 名前fの定義
void f() { }

さて、話を元に戻そう。これから学ぶのは$n$回"hello\n"sと出力するプログラムの書き方だ。ただし$n$はユーザーが入力するので実行時にしかわからない。すでに我々はユーザーから$n$の入力を受け取る部分のプログラムは書いた。

// n回出力する関数の宣言
void hello_n( int n ) ;

int main()
{
    // ユーザーからの入力
    int n {} ;
    std::cin >> n ;
    // n回出力
    hello_n( n ) ;
}

あとは関数hello_n(n)が$n$回"hello\n"sと出力するようなループを実行すればいいのだ。

すでに我々は無限回"hello\n"sと出力する方法を知っている。まずは無限回ループを書こう。

void hello_n( int n )
{
loop :
    std::cout << "hello\n"s ;
    goto loop ;
}

終了条件付きループで学んだように、このループを$n$回繰り返した場合に終了させるには、if文を使って、終了条件に達したかどうかで実行を分岐させればよい。

void hello_n( int n )
{
loop :
    // まだn回繰り返していない場合
    if ( ??? )
    { // 以下を実行
        std::cout << "hello\n"s ;
        goto loop ;
    }
}

このコードを完成させるにはどうすればいいのか。まず、現在何回繰り返しを行ったのか記録する必要がある。このために変数を作る。

int i = 0 ;

変数iの初期値は0だ。まだ繰り返し実行を1回も行っていないということは、つまり0回繰り返し実行をしたということだ。

1回繰り返し実行をするたびに、変数iの値を1増やす。

i = i + 1 ;

これはすでに学んだように、もっと簡単に書ける。

i += 1 ;

実は、さらに簡単に書くこともできる。変数の代入前の値に1を足した値を代入する、つまり変数の値を1増やすというのはとてもよく書くコードなので、とても簡単な演算子が用意されている。operator ++だ。

int main()
{
    int i = 0 ;
    ++i ; // 1
    ++i ; // 2
    ++i ; // 3
}

これで変数iの値は1増える。これをインクリメント(increment)という。

インクリメントと対になるのがデクリメント(decrement)だ。これは変数の値を1減らす。演算子はoperator --だ。

int main()
{
    int i = 0 ;
    --i ; // -1
    --i ; // -2
    --i ; // -3
}

さて、必要な知識は学び終えたので本題に戻ろう。$n$回の繰り返しをしたあとにループを終了するには、まずいま何回繰り返し実行しているのかを記録する必要がある。その方法を学ぶために、0, 1, 2, 3, 4...と無限に出力されるプログラムを書いてみよう。

このプログラムを実行すると以下のように表示される。

$ make run
1, 2, 3, 4, 5, 6, [Ctrl-C]

Ctrl-Cを押すまでプログラムは無限に実行される。

ではどうやって書くのか。以下のようにする。

  1. 変数iを作り、値を0にする
  2. 変数iと", "sを出力する
  3. 変数iをインクリメントする
  4. goto 2.

この処理を素直に書くと以下のコードになる。

int main()
{
    // 1. 変数iを作り、値を0にする
    int i = 0 ;
loop :
    // 2. 変数iと", "sを出力する
    std::cout << i << ", "s ;
    // 3. 変数iをインクリメントする
    ++i ;
    // 4. goto 2
    goto loop ;
}

どうやら、いま何回繰り返し実行しているか記録することはできるようになったようだ。

ここまでくればしめたもの。あとはgoto文を実行するかどうかをif文で条件分岐すればよい。しかし、if文の中にどんな条件を書けばいいのだろうか。

void hello_n( int n )
{
    int i = 0 ;
loop :
    // まだn回繰り返し実行をしていなければ実行
    if ( ??? )
    {
        std::cout << "hello\n"s ;
        ++i ;
        goto loop ;
    }
}

具体的に考えてみよう。n == 3のとき、つまり3回繰り返すときを考えよう。

  1. 1回目のif文実行のとき、i == 0
  2. 2回目のif文実行のとき、i == 1
  3. 3回目のif文実行のとき、i == 2
  4. 4回目のif文実行のとき、i == 3

ここではn == 3なので、3回まで実行してほしい。つまり3回目まではtrueになり、4回目のif文実行のときにはfalseになるような式を書く。そのような式とは、ズバリ"i != n"だ。

void hello_n( int n )
{
    int i = 0 ;
loop :
    if ( i != n )
    {
        std::cout << "hello\n"s ;
        ++i ;
        goto loop ;
    }
}

さっそく実行してみよう。

$ make run
3
hello
hello
hello
$ make run
2
hello
hello

なるほど、動くようだ。しかしこのプログラムにはバグがある。-1を入力すると、なぜか大量のhelloが出力されてしまうのだ。

$ make run
-1
hello
hello
hello
hello
[Ctrl-C]

この原因はまだ現時点の読者には難しい。この謎はいずれ明らかにするとして、いまはnが負数の場合にプログラムを0回の繰り返し分の実行で終了するように書き換えよう。

void hello_n( int n )
{
    // nが負数ならば
    if ( n < 0 )
        // 関数の実行を終了
        return ;

    int i = 0 ;
loop :
    if ( i != n )
    {
        std::cout << "hello\n"s ;
        ++i ;
        goto loop ;
    }
}

while文

goto文は極めて原始的で使いづらい機能だ。現実のC++プログラムではgoto文はめったに使われない。もっと簡単な機能を使う。ではなぜgoto文が存在するかというと、goto文は最も原始的で基礎的で、ほかの繰り返し機能はif文とgoto文に変換することで実現できるからだ。

goto文より簡単な繰り返し文に、while文がある。ここではgoto文とwhile文を比較することで、while文を学んでいこう。

無限ループ

無限ループをgoto文で書く方法を思い出してみよう。

int main()
{
    auto hello = []()
    { std::cout << "hello\n"s ; } ;

loop :
    // 繰り返し実行される文
    hello() ;
    goto loop ;
}

このコードで本当に重要なのは関数helloを呼び出している部分だ。ここが繰り返し実行される文で、ラベル文とgoto文は、繰り返し実行を実現するために必要な記述でしかない。

そこでwhile(true)だ。while(true)はgoto文とラベル文よりも簡単に無限ループを実現できる。

while (true) 文

while文は文を無限に繰り返して実行してくれる。試してみよう。

int main()
{
    auto hello = []()
    { std::cout << "hello\n"s ; } ;

    while (true)
        hello() ;
}

このコードの重要な部分は以下の2行。

while (true)
    hello() ;

これをgoto文とラベル文を使った無限ループと比べてみよう。

loop:
    hello() ;
    goto loop ;

どちらも同じ意味のコードだが、while文の方が明らかに書きやすくなっているのがわかる。

goto文で学んだ、ユーザーからの整数値の入力の合計の計算を繰り返すプログラムをwhile(true)で書いてみよう。

int input()
{
    std::cout << ">"s ;
    int x {} ;
    std::cin >> x ;
    return x ;
}

int main()
{
    int sum = 0 ;

    while( true )
    {
        sum += input() ;
        std::cout << sum << "\n"s ;
    }
}

重要なのは以下の5行だ。

while( true )
{
    sum += input() ;
    std::cout << sum << "\n"s ;
}

これをgoto文で書いた場合と比べてみよう。

loop :
    sum += input() ;
    std::cout << sum << "\n"s ;
    goto loop ;

本当に重要で本質的な、繰り返し実行をする部分の2行のコードはまったく変わっていない。それでいてwhile(true)の方が圧倒的に簡単に書ける。

終了条件付きループ

なるほど、無限ループを書くのに、goto文を使うよりwhile(true)を使った方がいいことがわかった。ではほかのループの場合でも、while文の方が使いやすいだろうか。

本書を先頭から読んでいる優秀な読者はwhile(true)のtrueはbool型の値であることに気が付いているだろう。実はwhile(E)の括弧の中Eは、if(E)と書くのとまったく同じ条件なのだ。条件がtrueであれば繰り返し実行される。falseなら繰り返し実行されない。

while ( 条件 ) 文
int main()
{
    // 実行されない
    while ( false )
        std::cout << "No"s ;

    // 実行されない
    while ( 1 > 2 )
        std::cout << "No"s ;

    // 実行される
    // 無限ループ
    while ( 1 < 2 )
        std::cout << "Yes"s ;
}

while文を使って、0が入力されたら終了する合計値計算プログラムを書いてみよう。

int input()
{
    std::cout << ">"s ;
    int x {} ;
    std::cin >> x ;
    return x ;
}

int main()
{
    int sum = 0 ;
    int x {} ;

    while( ( x = input() ) != 0 )
    {
        sum += x ;
        std::cout << sum << "\n"s ;
    }
}

重要なのはこの5行。

while( ( x = input() ) != 0 )
{
    sum += x ;
    std::cout << sum << "\n"s ;
}

ここではちょっと難しいコードが出てくる。whileの中の条件が、"( x = input() ) != 0"になっている。これはどういうことか。

実は条件はbool型に変換さえできればどんな式でも書ける。

int main()
{
    int x { } ;

    if ( (x = 1) == 1 )
        std::cout << "(x = 1) is 1.\n"s ;
}

このコードでは、"(x=1)"と"1"が等しい"=="かどうかを判断している。"(x=1)"という式は変数xに1を代入する式だ。代入式の値は、代入された変数の値になる。この場合変数xの値だ。変数xには1が代入されているので、その値は1、つまり"(x=1) == 1"は"1 == 1"と書くのと同じ意味になる。この結果はtrueだ。

さて、このことを踏まえて、"( x = input() ) != 0"を考えてみよう。

"( x = input() )"は変数xに関数inputを呼び出した結果を代入している。関数inputはユーザーから入力を得て、その入力をそのまま返す。つまり変数xにはユーザーの入力した値が代入される。その結果が0と等しくない"!="かどうかを判断している。つまり、ユーザーが0を入力した場合はfalse、非ゼロを入力した場合はtrueとなる。

while(条件)は条件がtrueとなる場合に繰り返し実行をする。結果として、ユーザーが0を入力するまで繰り返し実行をするコードになる。

goto文を使った終了条件付きループと比較してみよう。

loop:
    if ( (x = input() ) != 0 )
    {
        sum += x ;
        std::cout << sum << "\n"s ;
        goto loop ;
    }

while文の方が圧倒的に書きやすいことがわかる。

インデックスループ

$n$回"hello\n"sと出力するプログラムをwhile文で書いてみよう。ただし$n$はユーザーが入力するものとする。

まずはgoto文でも使ったループ以外の処理をするコードから。

void hello_n( int n ) ;

int main()
{
    int n {} ;
    std::cin >> n ;
    hello_n( n ) ;
}

あとは関数hello_n(n)がインデックスループを実装するだけだ。ただしnが負数ならば何も実行しないようにしよう。

goto文でインデックスループを書くときに学んだように、

  1. n < 0ならば関数を終了
  2. 変数iを作り値を0にする
  3. i != nならば繰り返し実行
  4. 出力
  5. ++i
  6. goto 3.

をwhile文で書くだけだ。

void hello_n( int n )
{
    // 1. n < 0ならば関数を終了
    if ( n < 0 )
        return ;

    // 2. 変数iを作り値を0にする
    int i = 0 ;

    // 3. i != nならば繰り返し実行
    while( i != n )
    {   // 4. 出力
        std::cout << "hello\n"s ;
        // 5. ++i
        ++i ;
    } // 6. goto 3
}

重要な部分だけ抜き出すと以下のとおり。

while( i != n )
{
    std::cout << "hello\n"s ;
    ++i ;
}

goto文を使ったインデックスループと比較してみよう。

loop :
    if ( i != n )
    {
        std::cout << "hello\n"s ;
        ++i ;
        goto loop ;
    }

読者の中にはあまり変わらないのではないかと思う人もいるかもしれない。しかし、次の問題を解くプログラムを書くと、while文がいかに楽に書けるかを実感するだろう。

問題：以下のような九九の表を出力するプログラムを書きなさい。

1	2	3	4	5	6	7	8	9	
2	4	6	8	10	12	14	16	18	
3	6	9	12	15	18	21	24	27	
4	8	12	16	20	24	28	32	36	
5	10	15	20	25	30	35	40	45	
6	12	18	24	30	36	42	48	54	
7	14	21	28	35	42	49	56	63	
8	16	24	32	40	48	56	64	72	
9	18	27	36	45	54	63	72	81

もちろん、このような文字列を愚直に出力しろという問題ではない。

int main()
{
    // 違う！
    std::cout << "1 2 3 4 5..."s ;
}

逐次実行、条件分岐、ループまでを習得した誇りある本物のプログラマーである我々は、もちろん九九の表はループを書いて出力する。

まず出力すべき表を見ると、数値が左揃えになっていることに気が付くだろう。

4	8	12
5	10	15

8は1文字、10は2文字にもかかわらず、12と15は同じ列目から始まっている。これは出力するスペース文字を調整することでも実現できるが、ここでは単にタブ文字を使っている。

タブ文字はMakefileを書くのにも使った文字で、C++の文字列中に直接書くこともできるが、エスケープ文字\tを使ってもよい。

int main()
{
    std::cout << "4\t8\t12\n5\t10\t15"s ;
}

エスケープ文字\nが改行文字に置き換わるように、エスケープ文字\tはタブ文字に置き換わる。

九九の表はどうやって出力すればよいだろうか。計算自体はC++では"a*b"でできる。上の表がどのように計算されているかを考えてみよう。

1*1	1*2	1*3	1*4	1*5	1*6	1*7	1*8	1*9	
2*1	2*2	2*3	2*4	2*5	2*6	2*7	2*8	2*9	
3*1	3*2	3*3	3*4	3*5	3*6	3*7	3*8	3*9	
4*1	4*2	4*3	4*4	4*5	4*6	4*7	4*8	4*9	
5*1	5*2	5*3	5*4	5*5	5*6	5*7	5*8	5*9	
6*1	6*2	6*3	6*4	6*5	6*6	6*7	6*8	6*9	
7*1	7*2	7*3	7*4	7*5	7*6	7*7	7*8	7*9	
8*1	8*2	8*3	8*4	8*5	8*6	8*7	8*8	8*9	
9*1	9*2	9*3	9*4	9*5	9*6	9*7	9*8	9*9

これを見ると、"a*b"のうちのaを1から9までインクリメントし、それに対してbを1から9までインクリメントさせればよい。つまり、9回のインデックスループの中で9回のインデックスループを実行することになる。ループの中のループだ。

while ( 条件 )
    while ( 条件 )
        文

さっそくそのようなコードを書いてみよう。

int main()
{
    // 1から9まで
    int a = 1 ;
    while ( a <= 9 )
    {
        // 1から9まで
        int b = 1 ;
        while ( b <= 9 )
        {
            // 計算結果を出力
            std::cout << a * b << "\t"s ;
            ++b ;
        }
        // 段の終わりに改行
        std::cout << "\n"s ;
        ++a ;
    }
}

うまくいった。

ところで、このコードをgoto文で書くとどうなるだろうか。

int main()
{
    int a = 1 ;
loop_outer :
    if ( a <= 9 )
    {
        int b = 1 ;
loop_inner :
        if ( b <= 9 )
        {
            std::cout << a * b << "\t"s ;
            ++b ;
            goto loop_inner ;
        }
        std::cout << "\n"s ;
        ++a ;
        goto loop_outer ;
    }
}

とてつもなく読みにくい。

for文

ところでいままでwhile文で書いてきたインデックスループには特徴がある。

試しに1から100までの整数を出力するコードを見てみよう。

int main()
{
    int i = 1 ;
    while ( i <= 100 )
    {
        std::cout << i << " "s ;
        ++i ;
    }
}

このコードを読むと、以下のようなパターンがあることがわかる。

int main()
{
    // ループ実行前の変数の宣言と初期化
    int i = 1 ;
    // ループ中の終了条件の確認
    while ( i <= 100 )
    {
        // 実際に繰り返したい文
        std::cout << i << " "s ;
        // 各ループの最後に必ず行う処理
        ++i ;
    }
}

ここで真に必要なのは、「実際に繰り返したい文」だ。その他の処理は、ループを実現するために必要なコードだ。ループの実現に必要な処理が飛び飛びの場所にあるのは、はなはだわかりにくい。

for文はそのような問題を解決するための機能だ。

for ( 変数の宣言 ; 終了条件の確認 ; 各ループの最後に必ず行う処理 ) 文

for文を使うと、上のコードは以下のように書ける。

int main()
{
    for ( int i = 1 ; i <= 100 ; ++i )
    {
        std::cout << i << " "s ;
    } 
}

ループの実現に必要な部分だけ抜き出すと以下のようになる。

// for文の開始
for (
// 変数の宣言と初期化
int i = 1 ;
// 終了条件の確認
i <= 100 ;
// 各ループの最後に必ず行う処理
++i )

for文はインデックスループによくあるパターンをわかりやすく書くための機能だ。例えばwhile文のときに書いた九九の表を出力するプログラムは、for文ならばこんなに簡潔に書ける。

int main()
{
    for ( int a = 1 ; a <= 9 ; ++a )
    {
        for ( int b = 1 ; b <= 9 ; ++b )
        { std::cout << a*b << "\t"s ; }

        std::cout << "\n"s ;
    }
}

while文を使ったコードと比べてみよう。

int main()
{
    int a = 1 ;
    while ( a <= 9 )
    {
        int b = 1 ;
        while ( b <= 9 )
        {
            std::cout << a * b << "\t"s ;
            ++b ;
        }
        std::cout << "\n"s ;
        ++a ;
    }
}

格段に読みやすくなっていることがわかる。

C++ではカンマ','を使うことで、複数の式を1つの文に書くことができる。

int main()
{
    int a = 0, b = 0 ;
    ++a, ++b ;
}

for文でもカンマが使える。九九の表を出力するプログラムは、以下のように書くこともできる。

int main()
{
    for ( int a = 1 ; a <= 9 ; ++a, std::cout << "\n"s )
        for ( int b = 1 ; b <= 9 ; ++b )
            std::cout << a*b << "\t"s ;
}

変数もカンマで複数宣言できると知った読者は、以下のように書きたくなるだろう。

int main()
{
    for (   int a = 1, b = 1 ;
            a <= 9 ;
            ++a, ++b,
            std::cout << "\n"s
        )
            std::cout << a*b << "\t"s ;
}

これは動かない。なぜならば、for文を2つネストさせたループは、$a \times b$回のループで、変数aが1から9まで変化するそれぞれに対して、変数bが1から9まで変化する。しかし、上のfor文1つのコードは、変数a, bともに同時に1から9まで変化する。したがって、これは単にa回のループでしかない。a回のループの中でb回のループをすることで$a \times b$回のループを実現できる。

for文では使わない部分を省略することができる。

int main()
{
    bool b = true ;
    // for文による変数宣言は使わない
    for ( ; b ; b = false )
        std::cout << "hello"s ;
}

for文で終了条件を省略した場合、trueと同じになる。

int main()
{
    for (;;)
        std::cout << "hello\n"s ;
}

このプログラムは"hello\n"sと無限に出力し続けるプログラムだ。"for(;;)"は"for(;true;)"と同じ意味であり、"while(true)"とも同じ意味だ。

do文

do文はwhile文に似ている。

do 文 while ( 条件 ) ;

比較のためにwhile文の文法も書いてみると以下のようになる。

while ( 条件 ) 文

while文はまず条件を確認しtrueの場合文を実行する。これを繰り返す。

int main()
{
    while ( false )
    {
        std::cout << "hello\n"s ;
    }
}

do文はまず文を実行する。しかる後に条件を確認しtrueの場合繰り返しを行う。

int main()
{
    do {
        std::cout << "hello\n"s ;
    } while ( false ) ;
}

違いがわかっただろうか。do文は繰り返し実行する文を、条件がなんであれ、最初に一度実行する。

do文を使うと条件にかかわらず文を1回は実行するコードが、文の重複なく書けるようになる。

break文

ループの実行の途中で、ループの中から外に脱出したくなった場合、どうすればいいのだろうか。例えばループを実行中に何らかのエラーを検出したので処理を中止したい場合などだ。

while ( true )
{
    // 処理

    if ( is_error() )
        // エラーのため脱出したくなった

    // 処理
}

break文はループの途中から脱出するための文だ。

break ;

break文はfor文、while文、do文の中でしか使えない。

break文はfor文、while文、do文の外側に脱出する。

int main()
{
    while ( true )
    {
        // 処理

        break ;

        // 処理
    }
}

これは以下のようなコードと同じだ。

int main()
{
    while ( true )
    {
        // 処理

        goto break_while ;

        // 処理
    }
break_while : ;
}

break文は最も内側の繰り返し文から脱出する

int main()
{
    while ( true ) // 外側
    {
        while ( true ) // 内側
        {
            break ;
        }
        // ここに脱出
    }
}

continue文

ループの途中で、いまのループを打ち切って次のループに進みたい場合はどうすればいいのだろう。例えば、ループの途中でエラーを検出したので、そのループについては処理を打ち切りたい場合だ。

while ( true )
{
    // 処理

    if ( is_error() )
        // このループは打ち切りたい

    // 処理
}

continue文はループを打ち切って次のループに行くための文だ。

continue ;

continue文はfor文、while文、do文の中でしか使えない。

int main()
{
    while ( true )
    {
        // 処理

        continue ;

        // 処理
    }
}

これは以下のようなコードと同じだ。

int main()
{
    while ( true )
    {
        // 処理

        goto continue_while ;

        // 処理

continue_while : ;
    }
}

continue文はループの最後に処理を移す。その結果、次のループを実行するかどうかの条件を評価することになる。

continue文は最も内側のループに対応する。

int main()
{
    while ( true ) // 外側
    {
        while ( true ) // 内側
        {
            continue ;
            // continueはここに実行を移す
        }
    }
}

再帰関数

最後に関数でループを実装する方法を示してこの章を終わりにしよう。

関数は関数を呼び出すことができる。

void f() { }

void g()
{
    f() ; // 関数fの呼び出し
}

int main()
{
    g() ; // 関数gの呼び出し
}

ではもし、関数が自分自身を呼び出したらどうなるだろうか。

void hello()
{
    std::cout << "hello\n" ;
    hello() ;
}

int main()
{
    hello() ;
}
  1. 関数mainは関数helloを呼び出す
  2. 関数helloは"hello\n"と出力して関数helloを呼び出す

関数helloは必ず関数helloを呼び出すので、この実行は無限ループする。

関数が自分自身を呼び出すことを、再帰(recursion)という。

なるほど、再帰によって無限ループを実現できることはわかった。では終了条件付きループは書けるだろうか。

関数はreturn文によって呼び出し元に戻る。単に'return ;'と書けば再帰はしない。そして、if文によって実行は分岐できる。これを使えば再帰で終了条件付きループが実現できる。

試しに、ユーザーが0を入力するまでループし続けるプログラムを書いてみよう。

// ユーザーからの入力を返す
int input ()
{
    int x { } ;
    std::cin >> x ;
    return x ;
}

// 0の入力を終了条件としたループ
void loop_until_zero()
{
    if ( input() == 0 )
        return ;
    else
        loop_until_zero() ;
}

int main()
{
    loop_until_zero() ;
}

書けた。

ではインデックスループはどうだろうか。1から10までの整数を出力してみよう。

インデックスループを実現するには、書き換えられる変数が必要だ。関数は引数で値を渡すことができる。

void g( int x ) { }
void f( int x ) { g( x+1 ) ; }

int main() { f( 0 ) ; }

これを見ると、関数mainは関数fに引数0を渡し、関数fは関数gに引数1を渡している。これをもっと再帰的に考えよう。

void until_ten( int x )
{
    if ( x > 10 )
        return ;
    else
    {
        std::cout << x << "\n" ;
        return until_ten( x + 1 ) ;
    }
}

int main()
{
    until_ten(1) ;
}

関数mainは関数until_tenに引数1を渡す。

関数until_tenは引数が10より大きければ何もせず処理を戻し、そうでなければ引数を出力して再帰する。そのとき引数は$+1$される。

これによりインデックスループが実現できる。

関数は戻り値を返すことができる。再帰で戻り値を使うことにより面白い問題も解くことができる。

例えば、1と0だけを使った10進数の整数を2進数に変換するプログラムを書いてみよう。

$ make run
> 0
0
> 1
1
> 10
2
> 11
3
> 1010
10
> 1111
15

まず10進数と2進数を確認しよう。数学的に言うと「10を底にする」とか「2を底にする」という言い方をする。

具体的な例を出すと10進数では1,2,3,4,5,6,7,8,9,0の文字を使う。1234は以下のようになる。

$$ 1234 = 1 \times 10^3 + 2 \times 10^2 + 3 \times 10^1 + 4 \times 10^0 = 1 \times 1000 + 2 \times 100 + 3 \times 10 + 4 \times 1 $$

10進数で1010は以下のようになる。

$$ 1010 = 1 \times 10^3 + 0 \times 10^2 + 1 \times 10^1 + 0 \times 10^0 = 1 \times 1000 + 0 \times 100 + 1 \times 10 + 0 \times 1 $$

2進数では1,0の文字を使う。1010は以下のようになる。

$$ 1010 = 1 \times 2^3 + 0 \times 2^2 + 1 \times 2^1 + 0 \times 2^0 = 1 \times 8 + 0 \times 4 + 1 \times 2 + 0 \times 1 $$

2進数の1010は10進数では10になる。

では問題を解いていこう。

問題を難しく考えるとかえって解けなくなる。ここではすでに10進数から2進数への変換は解決したものとして考えよう。関数convertによってその問題は解決した。

// 2進数への変換
int convert( int n ) ;

まだ我々は関数convertの中身を書いていないが、すでに書き終わったと仮定しよう。するとプログラムの残りの部分は以下のように書ける。

int convert( int n ) ;

// 入力
int input()
{
    std::cout << "> " ;
    int x{} ;
    std::cin >> x ;
    return x ;
}

// 出力
void output( int binary )
{
    std::cout << binary << "\n"s ;
}

int main()
{
    // 入力、変換、出力のループ
    while( true )
    {
        auto decimal = input() ;
        auto binary = convert( decimal ) ;
        output( binary ) ;
    } 
}

あとは関数convertを実装すればよいだけだ。

関数convertに引数を渡したときの結果を考えてみよう。convert(1010)は10を返し、convert(1111)は15を返す。

ではconvert(-1010)の結果はどうなるだろうか。これは-10になる。

負数と正数の違いを考えるのは面倒だ。ここでは正数を引数として与えると10進数から2進数へ変換した答えを返してくる魔法のような関数solveをすでに書き終えたと仮定しよう。我々はまだ関数solveを書いていないが、その問題は未来の自分に押し付けよう。

// 1,0のみを使った10進数から
// 2進数へ変換する関数
int solve( int n ) ;

すると、関数convertがやるのは負数と正数の処理だけでよい。

  1. 引数が正数の場合はそのまま関数solveに渡してreturn
  2. 引数が負数の場合は絶対値を関数solveに渡して負数にしてreturn
int convert( int n )
{
    // 引数が正数の場合
    if ( n > 0 )
        // そのまま関数solveに渡してreturn
        return solve( n ) ;
    else // 引数が負数の場合
        // 絶対値を関数solveに渡して負数にしてreturn
        return - solve( -n ) ;
}

nが負数の場合の絶対値は-nで得られる。その場合、関数solveの答えは正数なので負数にする。

あとは関数solveを実装するだけだ。

今回、引数の整数を10進数で表現した場合に2,3,4,5,6,7,8,9が使われている場合は考えないものとする。

// OK
solve(10111101) ;
// あり得ない
solve(2) ;

再帰で問題を解くには再帰的な考え方が必要だ。再帰的な考え方では、問題の一部のみを解き、残りは自分自身に丸投げする。

まずとても簡単な1桁の変換を考えよう。

solve(0) ; // 0
solve(1) ; // 1

引数が0か1の場合、単にその値を返すだけだ。関数solveには正数しか渡されないので、負数は考えなくてよい。すると、以下のように書ける。

int solve( int n )
{
    if ( n <= 1 )
        return n ;
    else
        // その他の場合
}

その他の場合とは、桁数が多い場合だ。

solve(10) ;  // 2
solve(11) ;  // 3
solve(110) ; // 4
solve(111) ; // 5

関数solveが解決するのは最下位桁だ。110の場合は0で、111の場合は1となる。最も右側の桁のみを扱う。数値から10進数で表記したときの最下位桁を取り出すには、10で割った余りが使える。覚えているだろうか。剰余演算子のoperator %を。

int solve( int n )
{
    if ( n <= 1 )
        return n ;
    else // 未完成
        return n%10 ;
}

結果は以下のようになる。

solve(10) ;  // 0
solve(11) ;  // 1
solve(110) ; // 0
solve(111) ; // 1

これで関数solveは最下位桁に完全に対応した。しかしそれ以外の桁はどうすればいいのだろう。

ここで再帰的な考え方が必要だ。関数solveはすでに最下位桁に完全に対応している。ならば次の桁を最下位桁とした数値で関数solveを再帰的に呼び出せばいいのではないか。

以下はsolve(n)が再帰的に呼び出す関数だ。

solve(10) ;  // solve(1)
solve(11) ;  // solve(1)
solve(100) ; // solve(10)→solve(1)
solve(110) ; // solve(11)→solve(1)
solve(111) ; // solve(11)→solve(1)

10進数表記された数値から最下位桁を取り除いた数値にするというのは、11を1に, 111を11にする処理だ。これは数値を10で割ればよい。

10  / 10 ; // 1
11  / 10 ; // 1
100 / 10 ; // 10
110 / 10 ; // 11
111 / 10 ; // 11

10進数表記は桁が1つ上がると10倍される。だから10で割れば最下位桁が消える。ところで、我々が計算しようとしているのは2進数だ。2進数では桁が1つ上がると2倍される。なので、再帰的に関数solveを呼び出して得られた結果は2倍しなければならない。そして足し合わせる。

int solve( int n )
{
    // 1桁の場合
    if ( n <= 1 )
        return n ; // 単に返す
    else // それ以外
        return
            // 最下位桁の計算
            n%10
            // 残りの桁を丸投げする
            // 次の桁なので2倍する
            + 2 * solve( n/10 ) ;
}

冗長なコメントを除いて短くすると以下のとおり。

int solve( int n )
{
    if ( n <= 1 )
        return n ;
    else
        return n%10 + 2 * solve( n/10 ) ;
}

再帰ではないループで関数solveを実装するとどうなるのだろうか。

引数の数値が何桁あっても対応できるよう、ループで1桁ずつ処理していくのは変わらない。

もう一度2進数の計算を見てみよう。

$$ 1010 = 1 \times 2^3 + 0 \times 2^2 + 1 \times 2^1 + 0 \times 2^0 = 1 \times 8 + 0 \times 4 + 1 \times 2 + 0 \times 1 $$

1桁目は0で、この値は$0 \times 2^0$、2桁目は1で、この値は$1 \times 2^1$になる。

一般に、$i$桁目の値は$i桁目の数字 \times 2^{i-1}$になる。

すると解き方としては、各桁の値を計算した和を返せばよい

int solve( int n )
{
    // 和
    int result = 0 ;
    // i桁目の数字に乗ずる値
    int i = 1 ;

    // 桁がなくなれば終了
    while ( n != 0 )
    {
        // 現在の桁を計算して足す
        result += n%10 * i ;
        // 次の桁に乗ずる値
        i *= 2 ;
        // 桁を1つ減らす
        n /= 10 ;
    }

    return result ;
}

再帰を使うコードは、再帰を理解できれば短く簡潔でわかりやすい。ただし、再帰を理解するためにはまず再帰を理解しなければならない。

再帰は万能ではない。そもそも関数とは、別の関数から呼ばれるものだ。関数mainだけは特別で、関数mainを呼び出すことはできない。

int main()
{
    main() ; // エラー
}

関数の実行が終了した場合、呼び出し元に処理が戻る。そのために関数は呼び出し元を覚えていなければならない。これには通常スタックと呼ばれるメモリーを消費する。

void f() { }            // gに戻る
void g() { f() ; }      // mainに戻る 
int main() { g() ; }

関数の中の変数も通常スタックに確保される。これもメモリーを消費する。

void f() { }

void g()
{
    int x {} ;
    std::cin >> x ;
    f() ;   // 関数を呼び出す
    // 関数を呼び出したあとに変数を使う
    std::cout << x ;
}

このコードでは、関数gが変数xを用意し、関数fを呼び出し、処理が戻ったら変数xを使っている。このコードが動くためには、変数xは関数fが実行されている間もスタックメモリーを消費し続けなければならない。

スタックメモリーは有限であるので、以下のような再帰による無限ループは、いつかスタックメモリーを消費し尽して実行が止まるはずだ。

void hello()
{
    std::cout << "hello\n" ;
    hello() ;
}

int main() { hello() ; }

しかし、大半の読者の環境ではプログラムの実行が止まらないはずだ。これはコンパイラーの末尾再帰の最適化によるものだ。

末尾再帰とは、関数のすべての条件分岐の末尾が再帰で終わっている再帰のことだ。

例えば以下は階乗を計算する再帰で書かれたループだ。

int factorial( int n )
{
    if ( n < 1 )
        return 0 ;
    else if ( n == 1 )
        return 1 ;
    else
        return n * factorial(n-1) ;
}

factorial(n)は$1 \times 2 \times 3 \times ... \times n$を計算する。

この関数は、引数nが1未満であれば引数が間違っているので0を返す。そうでない場合でnが1であれば1を返す。それ以外の場合、n * factorial(n-1)を返す。

このコードは末尾再帰になっている。末尾再帰は非再帰のループに機械的に変換できる特徴を持っている。例えば以下のように、

int factorial( int n )
{
    int temp = n ;

loop :
    if ( n < 1 )
        return 0 ;
    else if ( n == 1 )
        return temp * 1 ;
    else
    {
        n = n-1 ;
        temp *= n ;
        goto loop ;
    }
}

関数のすべての条件分岐の末尾が再帰になっているため、機械的に関数呼び出しをgoto文で置き換えることができる。

ただし、プログラミング言語C++の標準規格は、C++の実装に末尾再帰の最適化を義務付けてはいない。そのため、末尾再帰が最適化されるかどうかはC++コンパイラー次第だ。

再帰は強力なループの実現方法で、再帰的な問題を解くのに最適だが、落とし穴もある。