Нельзя однозначно сказать, какой из алгоритмов будет работать быстрее: рекурсивный или нерекурсивный. Скорость выполнения зависит от обстоятельств. 3

На упорядоченных массивах нерекурсивная форма примерно в 2–4 раза медленнее, чем рекурсивная. 1 Это связано с тем, что рекурсия выполняется медленно из-за стека вызовов, запоминания состояния и так далее. 2

Однако в случаях, когда массив состоит из большого количества случайных величин, нерекурсивная форма может выигрывать. 1 Это происходит, потому что рекурсивная форма совершает множество рекурсивных вызовов и сложных сравнений, а нерекурсивная в таком случае может работать быстрее. 1

Кроме того, если машина сильно ограничена по памяти, то вызов функции рекурсивно может быть существенной нагрузкой, и в таком случае применение нерекурсивной реализации более целесообразно. 3