再帰的に数えあげる方法の場合は、自然数を使っているのに実数を使っているからではないのですか。自然数＜実数ですよね。

その疑問は、カントールの対角線論法をさらに一歩深く、正しく捉えようとしているからこそ生まれる素晴らしい視点です！
結論から言うと、「自然数 < 実数」だからこそ、対角線論法で『はみ出し者（実数）』が作れたというのは100%正しいです。
しかし、ゲーデルが不完全性定理でやった本当の恐ろしさは、「実数なんていう巨大なものは一切使わず、1, 2, 3...という『自然数』のままで、対角線論法を使ってシステムを破壊した」という点にあります。
ここが最も勘違いしやすく、そして最も面白いポイントです。中学生でもスッキリ分かるように、2つのステップで整理します。

1. カントールの対角線論法（自然数 ＜ 実数）

カントールがやったのは、まさにあなたが言う通りのことです。
• 「自然数（1, 2, 3...）」の出席簿を作る。
• その出席簿に、「実数（0.1234...などの小数）」を全員載せようとした。
• 対角線論法を使ったら、出席簿（自然数）からはみ出す新しい小数（実数）が作れてしまった。
• だから、「自然数の数 < 実数の数」だということが証明された。
これは、「自然数という狭い箱」に「実数という無限に広いもの」を詰め込もうとしたから、あふれてしまった（はみ出した）わけです。

2. ゲーデルの悪魔的アレンジ（自然数 ＝ 自然数 なのにはみ出す）

では、ゲーデルの不完全性定理は何が違うのでしょうか？
ゲーデルは、「実数」を一切使いませんでした。 使うのは「自然数」だけです。
ここがマジックです。ゲーデルは、数学の「数式」や「証明のルール」を、すべて自然数の掛け算（素数の組み合わせ）に変換してしまいました。
• 数式の出席簿（1番の数式、2番の数式、3番の数式...）：すべて自然数。
• その中身（1, 2, 3...というルール）：これもすべて自然数。
「自然数の出席簿」に「自然数のルール」を載せているだけなので、カントールのように「実数の方が大きいからあふれる」ということは起きないはずです。同じ大きさ（自然数 ＝ 自然数）の箱なのだから、きれいに収まるはずです。
しかし、ゲーデルはここで「再帰的（ループする構造）」を使いました。
出席簿のななめ（対角線）を読み込んで、「わざと逆にする」という操作を、実数の小数点の代わりに、「自然数の数式の意味を反転させる」という形で行ったのです。
その結果、「自然数しか使っていないのに、自然数の出席簿からどうしてもはみ出してしまう『自然数の数式』」がポコッと生まれてしまいました。

まとめ：なぜ不完全性定理は衝撃だったのか？

あなたの直感はとても鋭いです。「実数を使っているからあふれる（はみ出す）」のであれば、それは「実数が大きすぎるからだね」という当たり前の話で終わります。
しかし、ゲーデルが証明したのは、
「実数のような恐ろしいものを使わず、1, 2, 3...という引き算や掛け算ができるだけのシンプルな『自然数の世界』であっても、対角線論法（再帰的なループ）を仕掛ければ、絶対にそのシステムでは証明できない穴（はみ出し者）が自動的に生まれてしまう」
ということでした。
だからこそ、当時の数学者たちは「実数なんて使っていない、完璧で安全なはずの足し算・掛け算の世界すら、不完全（穴だらけ）だったのか！」と絶望し、ひっくり返ったのです。
「同じ自然数を使っているのに、ルール（システム）のせいで、システムの外側にはみ出すものが作れてしまう」という不思議な現象、なんとなくイメージが湧きましたでしょうか？
このお話を踏まえて、次に気になるところはどこでしょう？
• ゲーデルがどうやって「数式を自然数（素数）に変身させたのか」（ゲーデル数のトリック）をのぞいてみる
• 「システムの中にいると、そのシステムを完璧にできない」というルールが、私たちの「言葉」や「思考」にどう影響しているかを考える
• 一番最初にお話しした「メビウスの帯（表が裏になる）」と、この「対角線で意味が反転する」ことのつながりを考えてみる