How to avoid input stack overflow during recursion

To make a tail recursive call you need to build the result token list from the other end:

\def\recursion#1#2{%
  \ifnum#1>#2
   \expandafter\eatv
  \else
    {#1}%
  \fi
  \expandafter\recursion\expandafter{\the\numexpr#1+1\relax}{#2}%
}

\def\eatv#1#2#3#4#5{}


\edef\result{{start}\recursion{0}{7000}} %works up to 4996

\show\result %`{Start}{0}{1}{2}{3}...'

\bye

Speaking slovenly: During recursion don't let your tokens go directly into the input-stack as the input-stack is small. Instead collect them within macro-arguments as the memory for macro-arguments usually is considerably larger.

\def\recursion#1{\innerrecursion{#1}{}}%

\def\innerrecursion#1#2{%
  \ifnum#1>0 %
    \expandafter\firstoftwo
  \else
    \expandafter\secondoftwo
  \fi
    {%
      \expandafter\innerrecursion
      \expandafter{%
      \number\numexpr #1-1\relax}{{#1}#2}%
    }{%  
      {Start}{0}#2%
    }%
}
\def\firstoftwo#1#2{#1}
\def\secondoftwo#1#2{#2}

\edef\result{\recursion{5000}}

\show\result %`{Start}{0}{1}{2}{3}...'

\bye

Define suitably \alex_repeat:n:

\input expl3-generic.tex

\ExplSyntaxOn
\cs_new:Npn \recursion #1
 {
  {Start}{0}
  \int_step_function:nnnN { 1 } { 1 } { #1-1 } \alex_repeat:n
 }
\cs_new:Npn \alex_repeat:n #1 { {#1} }
\ExplSyntaxOff

\edef\result{\recursion{5000}}

\show\result

\bye