基本情報技術者 試験情報＆徹底解説 -新制度に完全対応-

考えがまとまっていないのでとりあえず書き殴らせてください。
4ケタの2進数をすべて出力するプログラムが、どのような順番で出力するのかという問題です。

まず、解説ではより簡単な2桁の２進数の場合を考え、仕組みを捉えようとしていますが、まずその再帰的なプログラムをトレースするところからややこしいうえに非常に時間がかかり、難しすぎます。

<<2桁の２進数>>
binaryNumber(1)   //最初のbinaryNumber  
bin[1]←0  (0?)  
 binaryNumber(2)   //6行目のbinaryNumber @中断点① 
 bin[2]←0  (00) 
  binaryNumber(3)   //6行目のbinaryNumber @中断点②  
  printBin()  ※00を出力
  endif 【中断点②に戻る】
 binaryNumber(2)内、中断点②の次の行へ
 bin[2]←1 (01) 
  binaryNumber(3)   //8行目のbinaryNumber @中断点③ 
  printBin()  ※01を出力
  endif 【中断点③に戻る】
 binaryNumber(2)内、中断点③の次の行へ
 endif【中断点①に戻る】
binaryNumber(1) 内、中断点①の次の行へ
bin[1]←1（11）
  binaryNumber(2) //8行目のbinaryNumber @中断点④
  bin[2]←0（10）
  binaryNumber(3)  //6行目のbinaryNumber    @中断点⑤
  printBin()  ※10を出力
    endif 【中断点⑤に戻る】
  binaryNumber(2)内、中断点⑤の次の行へ
  bin[2]←1 (11)
    binaryNumber(3) //8行目のbinaryNumber    ＠中断点⑥
    printBin()  ※11を出力
    endif 【中断点⑥に戻る】
  binaryNumber(2)内、中断点⑥の次の行へ
  endif 【中断点④に戻る】
binaryNumber(1) 内、中断点④の次の行へ
endif 【これ以上戻れないので、終了】

出力されたコード [00,01,10,11]


さらに、この出力順が分かったところで、4ケタのときにどうなるかが推論できる力など到底ありません。
この問題だけ、他の問題との比にならないほどの地頭の良さ、閃きを要求されているような気がしていますが、解けるようになるのでしょうか。
この問題は、腰を据えて繰り返しじっくり解くだけでは、何の進展も改善も得られない気がします。

本を読んだことがない前提ですが、2進数をすべて出力する場合、常識外れのアルゴリズムにすることはまずありません。トレース例からすると、10進数順です。
4桁の場合も同様と思われますが、出力順としては、
[0000, 0001, 0010, 0011, 0100, ・・・, 1110, 1111]
と予想します。

そこから予想に合うようにアルゴリズムを読み解くわけですが、binに2進数の桁が入るものとすれば、LSB→MSBの桁に対応する配列bin[1], bin[2], bin[3], bin[4]に再帰を用いて順序よく0と1を入れていくようになると考えますが、いかがでしょうか。

再帰処理はだいぶめんどくさくはありますが問われているのは三行目までなのでbinaryNumber(5)まで行ってprintBin()を3回すればいいと思います。わたしは再帰処理があまりよく分かってなかったのですがこの問題のおかげで出来るようになりました。ちなみにですが0か1がはいるのでbinaryNumber(1)～binaryNumber(4)までで0か1をBinに入れてbinaryNumber(5)で1行分を出力するという形なのでBin [0,0,0,0]といった形で格納されていると思います。

トレースではないのですがαとβで入れる文字を変えてるだけなので三行目の元の数の0と1を入れ替えるだけで一応答えは出せるかなとは思います。

説明するの難しいですがいかがでしょう。

https://www.fe-siken.com/bbs/6125.html
と同じ手法で解説します。

3桁（n＝3）の場合で解説します。

test(3)を呼び出すと、binaryNumber(1)が呼び出される。
＋――――
｜（k＝1 つまり 1＜3 が偽なので 次のelse句を実行）
｜bin[1]←0
｜binaryNumber(1＋1) ★a
｜bin[1]←1
｜binaryNumber(1＋1) ★a
＋――――

上記★aの入れ子を展開すると次のようになる。
＋――――
｜（k＝1 つまり 1＜3 が偽なので 次のelse句を実行）
｜bin[1]←0
｜＋――――
｜｜（k＝2 つまり 2＜3 が偽なので 次のelse句を実行）
｜｜bin[2]←0
｜｜binaryNumber(2＋1) ★b
｜｜bin[2]←1
｜｜binaryNumber(2＋1) ★b
｜＋――――
｜bin[1]←1
｜＋――――
｜｜（k＝2 つまり 2＜3 が偽なので 次のelse句を実行）
｜｜bin[2]←0
｜｜binaryNumber(2＋1) ★b
｜｜bin[2]←1
｜｜binaryNumber(2＋1) ★b
｜＋――――
＋――――

上記★bの入れ子を展開すると次のようになる。
＋――――
｜（k＝1 つまり 1＜3 が偽なので 次のelse句を実行）
｜bin[1]←0
｜＋――――
｜｜（k＝2 つまり 2＜3 が偽なので 次のelse句を実行）
｜｜bin[2]←0
｜｜＋――――
｜｜｜（k＝3 つまり 3＜3 が偽なので 次のelse句を実行）
｜｜｜bin[3]←0
｜｜｜binaryNumber(3＋1) ★c
｜｜｜bin[3]←1
｜｜｜binaryNumber(3＋1) ★c
｜｜＋――――
｜｜bin[2]←1
｜｜＋――――
｜｜｜（k＝3 つまり 3＜3 が偽なので 次のelse句を実行）
｜｜｜bin[3]←0
｜｜｜binaryNumber(3＋1) ★c
｜｜｜bin[3]←1
｜｜｜binaryNumber(3＋1) ★c
｜｜＋――――
｜＋――――
｜bin[1]←1
｜＋――――
｜｜（k＝2 つまり 2＜3 が偽なので 次のelse句を実行）
｜｜bin[2]←0
｜｜＋――――
｜｜｜（k＝3 つまり 3＜3 が偽なので 次のelse句を実行）
｜｜｜bin[3]←0
｜｜｜binaryNumber(3＋1) ★c
｜｜｜bin[3]←1
｜｜｜binaryNumber(3＋1) ★c
｜｜＋――――
｜｜bin[2]←1
｜｜＋――――
｜｜｜（k＝3 つまり 3＜3 が偽なので 次のelse句を実行）
｜｜｜bin[3]←0
｜｜｜binaryNumber(3＋1) ★c
｜｜｜bin[3]←1
｜｜｜binaryNumber(3＋1) ★c
｜｜＋――――
｜＋――――
＋――――

上記★cはbinaryNumber(4)であり if (k ＞ n) が真なので printBin() の実行になる。
＋――――
｜（k＝1 つまり 1＜3 が偽なので 次のelse句を実行）
｜bin[1]←0
｜＋――――
｜｜（k＝2 つまり 2＜3 が偽なので 次のelse句を実行）
｜｜bin[2]←0
｜｜＋――――
｜｜｜（k＝3 つまり 3＜3 が偽なので 次のelse句を実行）
｜｜｜bin[3]←0
｜｜｜printBin() ★c
｜｜｜bin[3]←1
｜｜｜printBin() ★c
｜｜＋――――
｜｜bin[2]←1
｜｜＋――――
｜｜｜（k＝3 つまり 3＜3 が偽なので 次のelse句を実行）
｜｜｜bin[3]←0
｜｜｜printBin() ★c
｜｜｜bin[3]←1
｜｜｜printBin() ★c
｜｜＋――――
｜＋――――
｜bin[1]←1
｜＋――――
｜｜（k＝2 つまり 2＜3 が偽なので 次のelse句を実行）
｜｜bin[2]←0
｜｜＋――――
｜｜｜（k＝3 つまり 3＜3 が偽なので 次のelse句を実行）
｜｜｜bin[3]←0
｜｜｜printBin() ★c
｜｜｜bin[3]←1
｜｜｜printBin() ★c
｜｜＋――――
｜｜bin[2]←1
｜｜＋――――
｜｜｜（k＝3 つまり 3＜3 が偽なので 次のelse句を実行）
｜｜｜bin[3]←0
｜｜｜printBin() ★c
｜｜｜bin[3]←1
｜｜｜printBin() ★c
｜｜＋――――
｜＋――――
＋――――

結果として、n＝3の場合のこの例題は、次の命令を順に実行したら順に何が出力されるか、を問うています。
bin[1]←0
  bin[2]←0
    bin[3]←0
      printBin()  /* 000(改行)を出力 */
    bin[3]←1
      printBin()  /* 001(改行)を出力 */
  bin[2]←1
    bin[3]←0
      printBin()  /* 010(改行)を出力 */
    bin[3]←1
      printBin()  /* 011(改行)を出力 */
bin[1]←1
  bin[2]←0
    bin[3]←0
      printBin()  /* 100(改行)を出力 */
    bin[3]←1
      printBin()  /* 101(改行)を出力 */
  bin[2]←1
    bin[3]←0
      printBin()  /* 110(改行)を出力 */
    bin[3]←1
      printBin()  /* 111(改行)を出力 */

再帰処理の流れを理解する要点は、
地を這う虫のように一行一行トレースを始めるのではなく、
プログラムの開始から終了までの全体の流れはこうなる、と、
自分自身を呼び出す入れ子の関係の全体像をイメージすることだと考えます。
各命令の実行により変数がどう変化していくかをトレースするのはその後です。

ちなみに。
「地を這う虫のように」というのはトレース作業を揶揄しているのではなく、
鳥瞰図・虫瞰図、という日本語があるからそう形容しただけです。念のため。

> （k＝1 つまり 1＜3 が偽なので 次のelse句を実行）

あああ、if (k ＞ n) なので No.4の解説図の不等号の向きが全部逆でした。

たこ焼きさんのbinaryNumber(5)のprintbinを正直に3回やる方法で割と早めに解けるようになりましたし、「一直線で行ってこい」ではない、ジグザグに層が上下する再帰のトレースにも慣れてきました。
ただし、7行目とか10行目に出力されたものを聞かれても間違いなく時間制限を迎えて解けないと思います。

jjon-comさんのトレースを拝見して、改めてトレースだけで解くのは厳しいと感じました。
だからといって、何か万人向けの再現性のある解法(考え方)があるわけでもなさそうですし、応用問題なのである程度個人の地頭・本質の理解力が求められるのもしょうがないのかなと思いました。

何度もにらめっこしているうちに壁をブレイクスルーする瞬間があるそうなので、この問題も他の再帰の問題も繰り返し解く中で、トレースに頼らずに挙動がするりと理解できるようになると信じて精進します。