Early history of certain results on space-time tradeoffs?
I do not know if it is the first occurrence or not, but the construction appears in the proof of Lemma 1 of Borodin [Bor77] about the space complexity of evaluating a Boolean circuit.  (It contains slightly more than just the idea of recursive evaluation to reduce the space complexity further from O(D log S) bits to O(D + log S) bits, where D is the depth of the circuit and S is the size of the circuit.)

[Bor77] Allan Borodin.  On relating time and space to size and depth.  SIAM Journal on Computing, 6(4):733–744, Dec. 1977.  DOI: 10.1137/0206054.