How to discover a recursive relation in a data set? For a set of data, $x(n)$, where $n = 1, 2, 3, ...$, we know there are some kind of recursive relations among those data, $x(n)$ somehow depends on previous data $x(n-1), x(n-2), ...x(1)$, but we do NOT know what kind of recursive relations they are.
For example, recursive relations can be:
$$x(n) = x(n - 1) + x(n-2) $$
or
$$x(n) = x(n-1)x(n-2) + x(n-3)$$
or any other type of recursive relations.
Question:
Is there an algorithm to discover hidden recursive relations in a data set?
 A: There are fairly simple and fast methods for finding polynomials that match data exactly (As long as the data set size doesn't exceed 10^6, it'll work) (Newton-Gregory Interpolation, and much more, see 1. for a video on that topic), but assuming you want a simpler solution than the nth-degree polynomial that Newton-Gregory spits out, then a first guess is to throw it into OEIS - usually you'll find a sequence which is well defined, but not recursive - converting into a recursive relation shouldn't be too hard. 
If the internet doesn't give you any answers, then you could look into making a neural net that guesses an answer - no promises. The training data should be randomly generated recursively related sequences with simple rules. Then run it on the real deal - you should get a result pretty quickly. 
If that doesn't work - try doing a simple brute force search on a simpler version of the problem - restrict the recursions used, the operations used, and the past values used for the recursion, while allowing some mismatches in the data. (You won't find an exact solution using this way or the above.)
References:

*

*https://www.youtube.com/watch?v=4AuV93LOPcE
