Recursive to non recursive function

Question

$$ f(x) = \begin{cases} 0 & x=1 \\ f(x-1)+1 & \frac{f(x-1)}{x-1} < p \\ f(x-1) & \text{otherwise} \\ \end{cases} $$ Where $p$ is a constant less that or equal to 1. And x is a whole number greater than 0.

How do I get a non recursive solution for $f(x)$?

Answer 1

To make Nithin's answer more precise, we have $$f(x) = \begin{cases} \left\lceil (x-1) p \right\rceil & \text{ if } p \leq 1 \\ x - 1 & \text{ if } p > 1 \end{cases}$$

You can easily prove that by induction on $x$:

• If $x = 1$, then $f(x) = 0 = x-1 = \left\lceil (x-1)p \right\rceil$.
• If $p > 1$ and $f(x-1) = x - 2$, then we have $\frac{f(x-1)}{x-1} < p$, so we have $f(x) = x-2 + 1 = x-1$.
• If $p \leq 1$ and $f(x-1) = \left\lceil(x-2)p\right\rceil$, then there are two cases:
  • If $\frac{f(x-1)}{x-1} < p$, then we have $\left\lceil(x-2)p\right\rceil < (x-1)p$. Thus we have $f(x) = f(x-1)+1 = \left\lceil(x-1)p\right\rceil$.
  • Otherwise, we have $\left\lceil(x-2)p\right\rceil < (x-1)p$. So we have $f(x) = f(x-1) = \left\lceil(x-1)p\right\rceil$.