# How does one rewrite a recursive function to be strictly non-recursive?

Given the recursive function:

$$f(0) = \frac{x^2}{2} + \frac{x}{2}, f(n) = \frac{f(n-1)}{2} + \frac{x}{2}$$

where $x$ = some integer

How would one rewrite this function to be strictly non-recursive? Eg. the non-recursive counterpart to the recursive function $f(0) = x$, $f(n) = \large \frac{f(n-1)}{2}$ is $f(x)$ = $\large\frac{1}{2^{x}}$.

Thank you.

-
This a linear recurrence relation and there exists techniques for solving them. See here. –  Mhenni Benghorbal Jan 2 '13 at 22:35

$f(n)$ will be a linear function of $x^2$ and $x$. Looking at the first few terms $$f(1)=\frac{1}{4}x^2 + \frac{3}{4}x$$ $$f(2)=\frac{1}{8}x^2 + \frac{7}{8}x$$ etc., it is obvious $$f(n)=\frac{1}{2^{n+1}}x^2 + \left(1-\frac{1}{2^{n+1}}\right)x.$$ You can prove this by induction.

-
Thank you. This is the solution I was looking for. I appreciate it. –  user55003 Jan 2 '13 at 23:15

The terminology here is confused. Recursiveness is an intrinsic property of a function itself. Take for example the functions defined as follows:

$$f(0) = 1$$ $$f(n +1) = 2f(n)$$

and

$$g(n) = 2^n$$

It would be quite wrong to describe $g$ as a "non-recursive counterpart" to $f$. For $g$ is one and the very same recursive function as $f$. And $g$ is recursive precisely because it can be presented in the other way (which shows that $g$ belongs to the class of functions definable from the usual initial functions by composition, recursion and minimization),

We can talk about explicitly recursive vs closed form modes of presentation of a given function. But a function is recursive irrespective of how we present it. Thus take the function defined by

$$\mathit{fermat}(n) = 1 \mathrm{\ iff\ there\ are\ natural\ numbers\ } x, y, z \mathrm{\ such\ that\ } x^{n+3} +y^{n+3} = z^{n+3}$$ $$\mathit{fermat}(n) = 0 \mathrm{\ otherwise}$$

That's a bizarre presentation of what we now know, thanks to Andrew Wiles, is a recursive function -- the everywhere zero function!

-
Ah, thank you for the explanation. You see I only have a minimal grasp on high school algebra, being a young teenager. I knew what I wanted, I was just having trouble wording it so that any mathematician could understand. Thanks, I will keep this information in mind. –  user55003 Jan 2 '13 at 23:17