A sorozat valójában egy rekurzív függvény?

Hát, akár az is lehet, de nem feltétlen.

Nem. A sorozat valójában egy olyan függvény, amelynek értelmezési tartománya a pozitív egész számok halmaza. Ritkábban az értelmezési tartományba beletartozik a 0 is, még ritkábban a negatív egész számok.

Lehet diszkrét függvénynek is tekinteni, mert egy adott tartomány értékeihez egy-egy másik értéket rendel. Leginkább az elemek számításának megadása miatt kezeljük mégis külön, mert az adott elem nem feltétlenül csak az indexétől függ, hanem a kezdő vagy a szomszédos értékektől is. Valószínűleg így érted a rekurzív dolgot, de nem minden sorozat ilyen.

Minden sorozatot fel lehet írni rekurzív függvényként. Ha van egy sorozat, vegyük a szomszédos elemek különbségének sorozatát. Ezeket felhasználva könnyen fel lehet írni az eredeti sorozatot rekurzív függvényként (n. elem = n-1. elem + különbség sorozat n. eleme). Az más kérdés, hogy általában ennek sok értelme nincsen. A rekurzió, hogy korábbi elemtől is függ az aktuális érték, csak formaitás. Maga a rekurzív függvény definíciója is tartalmazhat egy végtelen sorozatot, ha a különbség sorozat nem egzakt, képlettel kifejezhető. De ez nem volt kikötés, hogy ilyen nem lehet.