1
$\begingroup$

Perhaps this is a question for stackoverflow because its practical nature, but I am not aware of any general method to relate recurrence relations and recursive functions.

Having as an example this recurrence relation:

$\qquad \begin{align}a_0 &= a_1 = 1 \\ 2a_n &= 3a_{n-1}-2a_{n-2}\end{align}$

I would like to transform it into a recursive function $f$, able to be called to itself a number of times (composite), i.e. $f \circ f \circ f \circ \dots \circ f$ ($n$ times), getting the same result as with the $a_n$ relation.

Any ideas about it?

$\endgroup$
  • 1
    $\begingroup$ I wonder why you need that; $n$-fold composition seems unnatural compared to recursion. Are you studying fixed-point theory? $\endgroup$ – Raphael Mar 23 '13 at 16:19
  • $\begingroup$ No, I am studying composition, but I'll probably find fixed point theory on the road.. $\endgroup$ – Hernan_eche Apr 10 '13 at 17:26
2
$\begingroup$
 static float f(int n,int m)
      {
         if((n==1)||(m==0)) return (1,1);
         return ((3*n - 2*m)/2,n);
      }

That way $\underbrace{f\circ f\circ \dots \circ f}_{\text{n times}} (1,0)=(a_n,a_{n-1})$.

Is that what you wanted?

$\endgroup$
  • $\begingroup$ what is return (1,1) ? it should return float? I am confused $\endgroup$ – Hernan_eche Apr 10 '13 at 17:22
  • $\begingroup$ @Hernan_e, it's the pair 1 1 not a float $\endgroup$ – wece Apr 11 '13 at 20:52
2
$\begingroup$

If I understand your question correctly, the function

$\qquad f(x) = \langle \frac{1}{2} \cdot (3x[1] - 2x[2]) , x[1] \rangle$,

with $\langle \cdot \rangle : \mathbb{N}^2 \to \mathbb{N}$ an encoding of tuples so that $a = \langle b, c \rangle \iff a[1] = b \land a[2] = c$, does the job in the sense that

$\qquad (\underbrace{f \circ \dots \circ f}_{n-1 \text{ times}})(\langle 1,1\rangle)[1] = a_n$

for $n \geq 2$. As implementation of $\langle \cdot \rangle$, you can use for instance Cantor's pairing method.

Note how above idea generalises easily: for a recurrence of degree $k$

$\qquad a_n = g(a_{n-1},\dots,a_{n-k}) + h(n)$,

use

$\qquad f(x) = \langle g(x[1], \dots, x[k]) , x[1], \dots, x[k-1] \rangle$.

$\endgroup$
  • $\begingroup$ It seems to be an answer, but I still cant translate it to a source code, I mean recursive programming function.. I can't understand what x[1] and x[2] are. $\endgroup$ – Hernan_eche Apr 10 '13 at 17:23
  • $\begingroup$ @Hernan_e I defined it in the third line; it denotes the inverse of the tuple encoding. $\endgroup$ – Raphael Apr 10 '13 at 18:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.