Что лучше при поиске чисел Фибоначчи - рекурсия или простое сложение?

Почему поиск чисел Фибоначчи решается с помощью рекурсии? В интернете много примеров с рекурсией - чем простое сложение не нравится? С рекурсией решается быстрее, если искать до 21 числа, а вот все что больше уже намного быстрее решается простым сложением. Почему с рекурсией быстрее, ведь это получается больше почти 100 раз вызов самого себя?
public static void main(String[] args) { long l = System.nanoTime(); long findFib = 16; System.out.println("not recursion = " + fib(findFib)); l = System.nanoTime() - l; System.out.println("time = " + l); l = System.nanoTime(); System.out.println("recursion = " + recFib(findFib)); l = System.nanoTime() - l; System.out.println("time = " + l); }
private static long fib(long i) { long curr = 1; long previous = 0; for (long j = 0; j < i - 1; j++) { long temp = curr; curr += previous; previous = temp; } return curr; }
private static long recFib(long i) { if (i < 2) { return i; } return recFib(i - 1) + recFib(i - 2); }

Ответ

Ваши два вопроса построены одинаково - спрашивается, почему о неверных вещах. Потому что это на самом деле не так.
В дидактических целях, чтобы показать, что такое рекурсия. Чтобы показать, что неразумное применение рекурсии ведет к неработоспособной программе. С рекурсией не быстрее никогда - по крайней мере для чисел Фибоначчи и без мемоизации.
Сравнение вот таких функций
long long fibR(unsigned int N) { if (N < 2) return 1; return fibR(N-1) + fibR(N-2); }
long long fibI(unsigned int N) { if (N < 2) return 1; long long f0 = 1, f1 = 1; for(unsigned int i = 2; i <= N; ++i) { long long f = f0 + f1; f0 = f1; f1 = f; } return f1; }
на моей машине дает (ссылка на полный код ниже; простите, я на C++ работаю, но не думаю, что на Java что-то изменится :))
N(i) = 3 3 0 mks N(r) = 3 3 1 mks N(i) = 6 13 0 mks N(r) = 6 13 5 mks N(i) = 9 55 0 mks N(r) = 9 55 22 mks N(i) = 12 233 0 mks N(r) = 12 233 95 mks N(i) = 15 987 0 mks N(r) = 15 987 406 mks N(i) = 18 4181 0 mks N(r) = 18 4181 1718 mks N(i) = 21 17711 0 mks N(r) = 21 17711 7301 mks N(i) = 24 75025 0 mks N(r) = 24 75025 24896 mks N(i) = 27 317811 0 mks N(r) = 27 317811 86819 mks N(i) = 30 1346269 0 mks N(r) = 30 1346269 370024 mks N(i) = 33 5702887 0 mks N(r) = 33 5702887 1568399 mks
Примерно тот же результат получается и тут: https://ideone.com/rfjifS