If you want to really delve into recursion, I recommend to learn a logic programming language like Prolog. Interestingly, Prolog programs are often efficient a

If you want to really delve into recursion, I recommend to learn a logic programming language like Prolog. Interestingly, Prolog programs are often efficient and general because, due to the power of unification, Prolog programs are more often tail recursive than functional programs. For example, we can define a relation called "append" in Prolog as follows: append([], Ls, Ls). append([A|As], Ls, [A|Rest]) :- append(As, Ls, Rest). In Prolog, recursion naturally arises by considering the inductive definitions of terms. For example, you can read the second clause as "If it is the case that append(As, Ls, Rest) holds, then it is also the case that append([A|As], Ls, [A|Rest]) holds". Note that such cases are not naturally tail recursive in Lisp, for example, because in languages that do not support unification of logical variables, there is one additional call of "cons" after the recursive call to construct the result. Also, the Prolog version is much more general and can be used in several directions! For this reason, "append" is not even a good name for such a relation, because it already implies one particular direction.