Primitive Recursion and course-of-values recursion - examples?
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$.