J, 16 19 12 characters
*/@$~/1,~$~/ or as a verb (17 characters):
h=:[:*/@$~/1,~$~/ usage:
h 2 4 65536 or taking input from keyboard (24 27 20 characters):
*/@$~/1,~$~/".1!:1]1 with thanks to FUZxxlFUZxxl for pointing out my stupidity. :-)
Explanation:
J is read from right to left, so using 2 4:
/ is used to insert the verb $~ between each pair of items in the list. $~ takes the left item and shapes it $ using the right item (the ~ reverses the arguments) - so this would be equivalent to 4 $ 2 which gives you a list of 2s which is four items long 2 2 2 2.
Now we append 1 to the list 1,~ and then do the same thing again; / insert a verb */@$~ between each pair of items in the list. This verb starts in the same way $~ but this time it / inserts a * between each item of the newly generated list. The @ just makes sure that the */@$~ works as one verb instead of two. This gives 2 multiplied by itself enough times to be equivalent to 2^4.
J's vocabulary page - I find solving problems with J fun just because of the different way it sometimes does things.
Adding one further iteration to remove the * operator has 2 problems
It comes out at 17 characters (+/@$~/,@$~/1,~$~/) which, even with the -5 bonus, is too long- It runs out of memory if the number gets too large so doesn't meet the requirement of being able to calculate
4 3