В Java рекурсивный вызов метода быстрее, чем итеративный

> компайлер превращает этот

$ /opt/java6/bin/javap -c recursion/RecursionTester > test

$ /opt/java6/bin/ -c recursion/TreeNode >> test

$ vi test

:)

>Хорошо бы посмотреть во что компайлер превращает этот якобы рекурсивный код.

Можно не смотреть - рекурсий не разворачивает.

А вот во что его превращает JIT вопрос отдельный.

>Вот только больно мне еэта формула не нравится, зачем floor вызывать, кога можно без него точную алгебраичскую формулу записать для a(n) ? Или подразумевалось, что считать будем на компутере а там корни вычисляются неточно ?

Да, floor(n+1/2) - это банальное округление. Правда, там точности не хватит. Только большие числа считаются достаточно точно. Та же единица даёт 0.7 с чем-то (утром считал, уже не помню точно).

> n-ое число Фибоначчи вообще считается за O(1) как floor(phi^n/sqrt(5)+1/2), где phi = (1 + sqrt(5))/2

распространенное заблуждение. Это О(lg n) в терминах операций с вещественными числами бесконечной точности. В компьютерах таких не бывает.

Неужто квадратный корень быстрее никак?

Но даже в этом случае оно явно смотрится лучше, чем O(n) :)

> Но даже в этом случае оно явно смотрится лучше, чем O(n) :)

гораздо красивее смотрится решение с возведением матрицы
 0 1
 1 1
в n-ю степень. Тоже O(lg n) но тут хоть оперировать нужно
целыми числами. Неограниченные целые проще реализовать чем
оценивать с какой погрешностью нужно вещественными числами
оперировать.

>Поправьте заголовок на "В Java итеративный вызов метода даже ещё медленнее, чем рекурсивный" пожалуйста.

+1 :)))

> Число ничуть не хуже pi в этом смысле.

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

Фи (1.618034) появляется из простейших алгебраический преобразований. Ну например, чтобы возвести фи в квадрат, надо просто прибавить к нему единицу. А чтобы вычислить обратное (1/n), надо просто отнять от него единицу.

Это всё из уравнения x^2 - x - 1 = 0 видно.