再帰の背後には、「スタック」と呼ばれるデータ構造が深く関わっています。関数が自分自身を呼び出すたびに、現在の実行状態（変数の値や次に実行するべき場所など）がコンピュータのメモリ上のスタック領域に保存されます。ベースケース（終了条件）に達して関数が値を返し始めると、スタックに積まれた実行状態が逆順に取り出され、計算が次々と完了していきます。このようにスタックを活用することで、複雑な状態管理をプログラム側ではなくシステム側に任せることができるのが再帰の強力な点です。一方で、再帰が深くなりすぎると、スタック領域のメモリ上限を超えてしまう「スタックオーバーフロー」という致命的なエラーが発生するリスクがあるため、扱うデータ量には注意が必要です。近年の一部の言語では、末尾再帰最適化と呼ばれる技術によって、このスタックオーバーフローを防ぐ工夫もされています。