Какие задачи сложно было бы решать в программе, не содержащей циклов?

Таких задач не существует. Любой цикл может быть заменён рекурсией.

Да, код может быть заметно медленнее (не все компиляторы умеют преобразовывать рекурсию в цикл, а затраты на рекурсию выше), но написать его было бы ненамного сложнее. Более того, в идеологически чистых функциональных языках всё делается рекурсией - без циклов.