You can convert any terminating formula (including recursive) to a finite logic representation in second order logic with exponential number of terms. This by use of Peano numbering.

Proving whether the given (inductive or recursive) formula is actually terminating is the halting problem though.

Linear logic is closely related to martingales too.