# How to write program to list all the function values without repeating?

Suppose I have a (recursive) function $f:\Bbb N\rightarrow\Bbb N$ whose range is infinite, and I want to list all the function values without repeating.

That is, if $f(0)=1,f(1)=1,f(2)=5,f(3)=6,f(4)=6,f(5)=2$, I need a program with outputs $1,5,6,2$ I need it to firstly list $1$, then $5$, then $6$ and then $2$.

My idea is: Start from $0$, firstly output $f(0)$, and then increase $0$ by $1$ to get $1$, look at what is $f(1)$, if it is equal to $f(0)$, then we do not output it, otherwise we output $f(1)$. And then look at $f(2)$, if it is equal to at least one of $f(0),f(1)$, then we do not write it out, otherwise we output $f(2)$. But so far I found my knowledge too poor to write a program in psudocode...

My attempt:

x := 0;

while (n < x)

{ if (f(n)=f(x));

n := n+1;

else

return f(x)}


I think maybe this code is problematic. Could someone please tell me some way to write it? This is such a minor part of my math course that we are not taught how to write psudocodes and now I feel a bit frustrated...

Other simple ways to do it would also be appreciate. Thanks in advance to you all who may help!

To sum up, I wish to see a psudocode to out put all the values of the function:

$f':\text{n↦the nth value in the enumeration that isn't a repeat of a previous value}$ where $f$ is a recursive function. Apologize for my poor knowlege of computing. I have no backgroud of computing and even not know what is "memory", only psudocode is readable for me... And actually I just need the psudocode program to prove that this function is recursive.

• Keep in mind that, if the image of $f$ contains only finitely many values, after you have listed them all, the listing program has to diverge -- there's no way to check that we have listed them all, so the listing program has to query $f$ forever just in case some new value appears. This argument is not a proof, but at least can provide some intuition. – chi Jul 17 '17 at 15:09
• What is your question? Do you want a code in a certain programming language? Do you want just an algorithm and you want to code it yourself? As far as I understand you want to display the range of the function, so what if the range is infinite? – fade2black Jul 17 '17 at 15:40
• Seems like a programming question to me? – Raphael Jul 17 '17 at 20:16
• Hint: use memory. – Raphael Jul 17 '17 at 20:17
• @Raphael Yes, that's what I meant. My point is that, if the "index of the function value we want" is larger than the number of distinct elements that $f$ produces, then the enumeration has to diverge. (This is not as issue per se, but something to keep in mind anyway) – chi Jul 17 '17 at 20:22

You can implement your task by keeping track of the values that have appeared so far. You maintain an array $S$ that starts empty. You compute the values $f(0),f(1),f(2),\ldots$, and for each value, you check whether it is already in $S$; if so, you don't do anything; otherwise, you print it, and add it to $S$.
• That is only an assumption, but the OP should stipulate that the range of the function is finite. For example, the range $f(0) = 0, f(n) = n + f(n-1)$ is infinite. Or I am missing something. – fade2black Jul 17 '17 at 15:51
• No, I disagree. The set $\{f(0),\ldots,f(n)\}$ is finite for every $n$. – Yuval Filmus Jul 17 '17 at 15:51