> In the equivalent of my recurrence equations implementation, the
> macro \f:n is defined _after_ the substitution. The error complains
> about \f:n not being defined. Defining \f:n _before_ the substitution
> works fine.

The problem is that you \tl_use:N \l_expr_tl before defining \f:n. If
you look at which line the error occurs, this is the line. To display
a token list to the terminal (or log file), use one of the lines

\tl_show:N \l_expr_tl
\iow_term:x { \tl_to_str:N \l_expr_tl }
\iow_log:x { \tl_to_str:N \l_expr_tl }

Those differ in the details, but give you the information without
expanding the token list: the last two lines convert the token list to
a string of characters before printing them to the terminal or the log
file. On the other hand, \tl_use:N is like typing the token list in
your file. It will then be run as normal code, in particular expanding
macros, including \f:n which is not defined yet.

> In my recurrence equation implementation, defining \f:n _after_ the
> substitution is possible, but it requires a bit more work. Does \f:n
> have to be known at substitution time?

It does not have to be defined at substitution time, but at use time. See below.

-- 

\documentclass{article}
\usepackage{xparse,l3regex}
\begin{document}

\ExplSyntaxOn

\tl_new:N \l_name_tl
\tl_set:Nn \l_name_tl {f}
\tl_new:N \l_expr_tl
\tl_set:Nn \l_expr_tl {f{i}}

\iow_term:x { before:~\tl_to_str:N \l_expr_tl }
\iow_term:x { and~\tl_to_str:N \l_name_tl }

\regex_replace_all:nnN
  {\b\u{l_name_tl}\b} {\c{\u{l_name_tl}:n}} \l_expr_tl

\iow_term:x { after:~\tl_to_str:N \l_expr_tl }
\iow_term:x { and~\tl_to_str:N \l_name_tl }

% Define \f:n before using it! :-)
\cs_new_nopar:cpx { \l_name_tl :n } #1{}
after(\tl_use:N \l_expr_tl)

\end{document}

-- 
Regards,
Bruno