Why an upside down path on the evaluation of branching program on encrypted data?
The "omitted part of this upside down algorithm" is like dynamic programming, since it

computes node values before getting to the point at which those values will be used.

Unlike my original thought, the recursive approach certainly can be better; the canonical

example of that would be using their scheme for PIR. $\:$ However, for the application your

previous question was about, their approach will definitely be better than recursion.

$P$ is just a party's input, so it certainly can be reused. $\:$ However, the resulting

ciphertext can't necessarily be run through the homomorphing process again, since the

group changes with each layer. $\:$ (That is mentioned in the top paragraph of page 16.)