I ran into examples that I not trivially understand on course-of-values recursion,

In defining a function by primitive recursion, the value of the next argument $f(n+1)$ depends only on the value of the current argument $f⁢(n)$. Definition of functions by course-of-values recursion, $f⁢(n+1)$ depends on value(s) of some or all of the preceding arguments $f⁢(n),…,f⁢(0)$. very basic examples of definition by course-of-values recursion are Fibonacci numbers...

My examples, from the computation course, wrote following $f_1$ and $f_2$ is Primitive recursive. I reproduce them here:

Let $g$ be a primitive recursive function,

  1. $f_1(0)=c_1, f_1(1)=c_2, f_1(x+2)=g(x,f_1(x),f_1(x+1))$, and

  2. $f_2(x)=c, f_2(x+1)=g(x,[f_2(0),...,f_2(x)])$ are primitive recursive.

I couldn't say how $f_1$ and $f_2$ are Primitive Recursive? any idea to finding these are P.R.?

Edit 1: after the Yuval Hint the $f_1$ is easy, but for $f_2$ there is a problem, I try more than three days, but not capable to create an easy encode for $f_2$. any hint or idea?

  • For $f_2$, presumably the base case is $f_2(0) = c$ rather than $f_2(x) = c$. – Yuval Filmus Mar 27 '15 at 22:17

The idea is to use some appropriate coding. A primitive recursive encoding of pairs is an encoding $\mathbb{N}^2 \to \mathbb{N}$, denoted by $\langle x,y \rangle$, such that the following functions are recursive: $e(x,y) = \langle x,y \rangle$, $p_1(\langle x,y \rangle) = x$, $p_2(\langle x,y \rangle) = y$. Coming up with a primitive recursive encoding of pairs is tedious but possible. Using such an encoding you can implement the first type of recursion in your question. The second type uses a more elaborate encoding scheme, which you can figure out on your own.

More explicitly, here is how you would implement a recursion of the first type: $$ G(x,y) = \langle p_2(y), g(x,p_1(y),p_2(y)) \rangle \\ h(0) = \langle c_1,c_2 \rangle, \quad h(x+1) = G(x,h(x)) \\ f_1(x) = p_1(h(x)) $$ The trick in this case is that instead of computing the function $f_1$ itself, we compute the function $h(x) = \langle f_1(x), f_1(x+1) \rangle$; the value of $h$ at the point $x+1$ only depends on its value at the point $x$.

For the second type, similarly we compute the function $k(x) = [f_2(0),\ldots,f_2(x)]$ instead of $f_2$ itself; the value of $k$ at the point $x+1$ only depends on its value at the point $x$.

  • Comments are not for extended discussion; this conversation has been moved to chat. – Raphael Mar 29 '15 at 8:48
  • Dr. Yuval at first thanks again. if you are sure this is not homework after three days would you please complete it to learn me? if you suspect please complete it after one month :) thanks Dr. – LogicLove Mar 30 '15 at 19:40
  • is it possible to clear (2) for me with completing it Dr ? – LogicLove Apr 1 '15 at 12:29
  • WOULD YOU PLEASE UPDATE FOR 2? – LogicLove Apr 15 '15 at 14:58

Your Answer


By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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