What you are seeing (well, not seeing) is exponential computational complexity.

Clear[s, t]
s[1] = 3;
s[2] = 5;
t[1] = 1;
s[n_] := t[n - 1] - t[n - 2] + 4
t[n_] := t[n - 1] + s[n - 1]
Table[Timing[t[n]], {n, 10, 30, 5}]

(* Out[257]= {{0., 100}, {0.012000, 225}, {0.208000, 400}, {4.396000,  625}, {92.460000, 900}} *)

For one remedy, see tutorial/FunctionsThatRememberValuesTheyHaveFound in the documentation center. Other approaches would include doing explicit iterations or recasting as a matrix power.