\documentclass[12pt]{article} 

\usepackage[paper=a4paper,landscape]{geometry}
\usepackage{recurrence} 

\begin{document} 

\section{Start}

%\tracingmacros=1
   \NewRecDef{f[0]=1,
              f[1]=1,
              f[i]=f[i-1]+f[i-2]}


\begin{tt}
\begin{tabular}{ll}
   f   & \meaning\f
\\ f:n & \expandafter\meaning\csname f:n\endcsname
\\ recurrence\_f\_0:n & \expandafter\meaning\csname recurrence_f_0:n\endcsname
\\ recurrence\_f\_1:n & \expandafter\meaning\csname recurrence_f_1:n\endcsname
\\ recurrence\_f\_2:n & \expandafter\meaning\csname recurrence_f_2:n\endcsname
\\ recurrence\_f\_3:n & \expandafter\meaning\csname recurrence_f_3:n\endcsname
\end{tabular}
\end{tt}

\ExplSyntaxOn

\f{0},
\f{1},
% \f{2} % fails

\cs_set_nopar:cpn {recurrence_f_2:n} #1 {
    \bool_if:nTF { \c_true_bool }{\f:n{#1-1}+\f:n{#1-2}}{\recurrence_f_3:n {#1}}
}

\f{2},
\f{3},
\f{4},
\f{5},
\f{6},
\f{7},
\f{8},
\f{9},
\f{10},
\f{11},
\f{12},
\f{13},
\f{14},
\f{15},
\f{16},
\f{17},
\f{18},
\f{19},
\f{20},
\f{21 - 1},


\end{document}

