De ce contează?
Stai la fereastră și vrei să prezici câte mașini trec în minutul următor. Nu te uiți la tot istoricul zilei — îți ajung ultimele câteva minute, pe care le ții minte și le „rostogolești”: când vine un minut nou, îl uiți pe cel mai vechi. Memoria ta rămâne de aceeași mărime, oricât de lungă e ziua. Un șir recurent funcționează identic: fiecare termen nou se naște dintr-o fereastră scurtă de termeni recenți, nu din tot șirul.
Intuiția
La Fibonacci, fiecare termen e suma ultimilor doi. Dar regula poate privi mai înapoi: la Tribonacci fiecare termen e suma ultimilor trei. În general, o recurență poate depinde de ultimii K termeni. Ideea-cheie e mereu aceeași: ca să produci termenul următor nu ai nevoie de tot șirul, ci doar de o fereastră cu cei mai recenți K termeni, pe care o gliseezi spre dreapta.
Păstrezi doar ultimii K termeni — o fereastră de mărime fixă. Când produci unul nou, îl arunci pe cel mai vechi. Memoria nu crește cu lungimea șirului, ci rămâne O(K): la Fibonacci K = 2, la Tribonacci K = 3.