Can the output value be solved and/or written as Taylor expansion?
It is better to use as parameters maxDepth-currentDepth, n, k. Call the resulting function $f_k(d,n)$.

When $k = 0$,
$$
f_0(d,n) = \begin{cases}
n &amp; d = 0, \\
f_0(d-1,f_0(d-1,n)) &amp; d &gt; 0.
\end{cases}
$$
You can prove by induction that the solution is $f_0(d,n) = n$.

When $k=1$,
$$
f_1(d,n) = \begin{cases}
n &amp; d = 0, \\
f_1(d-1,f_0(d-1,n)) + f_0(d-1,f_1(d-1,n)) &amp; d &gt; 0,
\end{cases}
$$
which reduces to
$$
f_1(d,n) = \begin{cases}
n &amp; d = 0, \\
2f_1(d-1,n) &amp; d &gt; 0.
\end{cases}
$$
The solution is
$$
f_1(d,n) = 2^d n.
$$
When $k = 2$, using the preceding formulas we get
$$
f_2(d,n) = \begin{cases}
n &amp; d=0, \\
2f_2(d-1,n) + 4^{d-1} n &amp; d &gt; 0.
\end{cases}
$$
Unrolling the recursion gives
$$
\begin{align*}
f_2(d,n) &amp;= 4^{d-1} n + 2\cdot 4^{d-2} n + 2^2 \cdot 4^{d-3} n + \cdots + 2^{d-1} n + 2^d n \\ &amp;=
(2^{2d-2} + 2^{2d-3} + \cdots + 2^{d-1}+2^d) n \\ &amp;=
(2^d+1)2^{d-1} n.
\end{align*}
$$
Let us approximate this by $2^{2d-1}n$.

When $k = 3$, the preceding formulas show that
$$
f_3(d,n) \approx
\begin{cases}
n &amp; d = 0, \\
2f_3(d-1,n) + 2^{3d} n &amp; d &gt; 0.
\end{cases}
$$
Unrolling the recursion gives
$$
f_3(d,n) \approx (2^{3d} + 2^{3(d-1)+1} + 2^{3(d-2)+2} + \cdots + 2^{3(1)+d-1} + 2^d)n \approx \frac{4}{3} 2^{3d}n. 
$$
Continuing in this way, we find that up to constants, if $f_k(d,n) = \Theta(2^{r_kd}n)$ then $r_{k+1} = \max_{1 \leq \ell \leq k} (r_\ell + r_{k+1-\ell})$ (except for the base cases $k \leq 1$). For example, we have
$$
\begin{align*}
&amp;r_0 = 0 \\
&amp;r_1 = 1 \\
&amp;r_2 = 2 \\
&amp;r_3 = 3 \\
&amp;r_4 = 4
\end{align*}
$$
and so on. Indeed, induction shows that $f_k(d,n) = \Theta_k(2^{kd}n)$. With more effort, we could estimate the hidden constant.