この問題は 再帰 (recursion) を使って解いてくれることを期待して（再帰を理解しているかどうかを見るために）出題した．

問題文の絵を眺めていると，直ぐに次のことに気付くであろう．総数 ~n~ 個の正方形を指定されているような辞書式順序で，一番左に ~m~ 個以下の正方形が積まれているように並べる並べ方を ~F(n, m)~ で表すことにすると，次のような漸化式（再帰方程式）が得られる：

• ~F(0, m) =~
  • 何もしない
• ~F(n, m) =~
  • [~m~ 個の正方形を縦に積む] ~F(n-m, m)~ ;
  • [~m-1~ 個の正方形を縦に積む] ~F(n-m+1, m-1)~ ;
  • …
  • [~m-i~ 個の正方形を縦に積む] ~F(n-m+i, m-i)~ ;
  • …
  • [~1~ 個の正方形を置く] ~F(n-1, 1)~ ;

これをそのまま再帰的なプログラムとして書けばよい（[　] の部分では出力を行う）．

このような 2 変数の再帰を思い付けば問題ないが，以下では，~n~ だけに注目した再帰しか思いつかなかった場合についても考えてみよう．求める並び方を求める関数を ~f(n)~ とする．~f(n)~ では，上記で [　] の部分を実行するのと同じ順序で，正方形の並べ方を記録に残しておいて，~f(0)~ のときにその記録を出力する（実は，この方法は本質的に上述の方法と同じものである）．この "記録" を行うためには スタック (stack) を用いる．

上述の 2 つの再帰的アルゴリズムのいずれにおいても再帰には重複する計算がないので，実行時間は ~n~ に比例する時間しかかからない．