The Ackermann function
A function suggested by Ackermann as an example for a recursive function cannot be written as an iterated function.
According to Professor David Brailsford this is one of the most difficult functions to evaluate if not the most (except the Busy Beaver).
It's estimated that in the time takes to calculate ack(4, 4) the whole time between the big bang and the big crunch will pass, but for any pair of number the ack function will not go to an infinite loop.