If a program doesn't include any loop, recursion or equivalent construct, then it cannot express recursive computations.
In order to write a formal proof, you'd need to define your language formally. “Equivalent construct” can include some exotic things such as parallel execution, exception handlers, higher-order functions (leading to fixpoint combinators), meta-execution facilities (
eval), etc. that let recursion in through a backdoor.
Suppose that a language contains only the following constructs: constants, assignments, sequence (do a then do b), functions operating on base types (but not functions taking functions as arguments), conditionals (
if (x == y)), some primitives on base types (e.g.
*). Then the execution of the program takes a time that is at most exponential, and in particular bounded, in the size of the program (the unit of time is an elementary expression, e.g.
x := y takes one unit,
x := y + z takes two units). In a nutshell, function application at most multiplies the complexity of the function by the complexity of the program, and the rest is linear.
Since this language can only express bounded-time computations, it cannot express all recursive programs (and in fact it cannot even express all primitive recursive programs).