I'm not sure if my wording is entirely correct, but I was just wondering if every recursive formula can be turned into an explicit formula.
I am asking this because various sources online gives me opposite answers. Although, one thing I have noticed is that every source likes to use different words other than "formula", like "expression" and such.
According to wiki, "Although not all recursive functions have an explicit solution"
So I guess another part of my question is :
What difference is it when people say recursive function, expression, formula, etc. (if there is any)
But yeah, I have seen a stackoverflow post saying that every recursion can be turned into an iteration, and doesn't this also mean everything can be explicitly defined?
Best Answer
You are reading about two different things. There are recursive functions in math, and there are recursive functions in computer programming. Programming is a form of math, but never mind that. In general, a recursive function where $f(n) = g(n, f(n-1), f(n-2), \ldots)$ can not always be converted to an explicit form. On the other hand, a recursive function in a computer program can be converted to a non-recursive (iterative) function. This is due to a rather trivial solution where the program's call stack is imitated in an iterative function.