(Initially this question was on cstheory, but I was told cs would be a better fit, so posting it here.)
All other things being equal, which of the following languages would be more challenging to design a compiler and/or interpreter for? (If the answer would vary depending on whether one is designing a compiler or interpreter, please address that difference.)
Language 1: Supports recursion but not higher-order functions in any sense, not even C-language qsort function-as-parameter style, let alone functions as a return value.
Language 2: Supports higher-order functions, but not recursion. Higher-order meaning that a function is allowed to both take functions as inputs as well as return functions.
-- Some answers from post on cstheory: recursion is trivial. It amounts to backwards jumps and a bit of care with the stack and stack frames. Support for full higher order functions, especially if you want to be efficient needs a bit of care, you need things like closures (or compile higher-orderness away).
When your code needs to return a function, and that function captures some local data, then you don't know in advance the lifetime of that local data. This forces you either into garbage collection, or into sophisticated reference counting / lifetime tracking, or full-blown ownership types like in Rust, or something like this. Objective C and Swift have trouble with closures, due to this problem with unknown lifetimes of memory allocated data.