Does Tail Recursion will be an optimization in php

Question

by this question: Does PHP optimize tail recursion?

php will not optimize the tail recursion

but when I try on my machine, (php 5.3.10)

two programs for fibonacci: one is normal recursion, another is tail recursion

the time programs used differs a lot:

and I feel confused about that, who can tell me why the tail recursion is faster then normal recursion, if php does not optimize it？

fibonacci.php:

<?php
function fibonacci($n) {
    if ($n < 2) {
        return $n; 
    }   
    return fibonacci($n - 1) + fibonacci($n - 2); 
}
var_dump(fibonacci(30));

fibonacci2.php:

<?php
function fibonacci2($n, $acc1, $acc2) {
    if ($n == 0) {
        return $acc1;
    }   
    return fibonacci2($n-1, $acc2, $acc1 + $acc2);
}

var_dump(fibonacci2(30, 0, 1));

Please, show source code for both scripts. – Oroboros102 Jul 09 '12 at 07:00 — Oroboros102, Jul 09 '12 at 07:00
hi, i had add script for that – jianfeng Jul 10 '12 at 01:22 — jianfeng, Jul 10 '12 at 01:22

score 2 · Accepted Answer · answered Jul 10 '12 at 01:33

The second script is faster because it recurses fewer total times, not because it uses tail recursion.

(The first script calls itself twice at each level. The second script only calls itself once at each level. As such, the second script simply ends up doing far less work than the first one.)

Does Tail Recursion will be an optimization in php

1 Answers1