R
@Applied-Mediocrity Now that you mention it, I did not want to be overly ic previously, but this is where things get interesting.
Indeed, it's a recursive things, so to prove you're French, all you need to do is find one proven French ancestor, and a direct line of always-born-in-France in between. The second bit is fairly easy, we've had overall reliable registers for at least 200 years or more (there are always some missing ones e.g. archives burnt during the wars, but overall, as long as it stays inside France, almost anyone can track back direct ancestry up to at least the French Revolution if not earlier).
So you're left with proving that that one ancestor was French. I think (from experience, but I don't know the exact legal basis) that a great-grand-parent born and married in France (and all intermediate links to them being also) is taken as an implicit proof that they were French. Or maybe you need at least X great-grand-parents to be in that case. More likely since it's ruled by a judge (see above...), you show proofs of that for as many ancestors as you can, and the judge decides whether at least one of them was French, on that basis. That's how it would work for most people where the administration has a doubt and asks you to prove it, I believe.
There are some interesting edge cases though: in 1870 the Crémieux Decree (named after the justice minister who pushed it) granted French nationality to all Jews living in (relatively recently colonised) Algeria. So if you track back your ancestry to one such person (and you and your parents etc. were born in France, or in French Algeria), then you're French. There has been at least one case where the highly secular French Republic asked someone to prove that they were of a specific religion (i.e. Jew), which is normally a huge no-no, in order to determine whether this person was French or not.