0

I was watching: https://www.youtube.com/watch?v=_JtPhF8MshA

Where the following implementation:

int factorial (int n)
{
    if (n==0) return 1;
    return n * factorial(n-1);
}

with the following:

int factorial (int n)
{
    return go(n, );
}

int go(int n, int a)
{
    if (n==0) return a;
    return go(n-1, a*n);
}

Where he claimed the second is more efficient but my question is why?

Both call the function exactly the same number of times, thus 2 of them are O(n).

Daniel
  • 1
  • Because the first of deep down `n` time deeper than the second one in the "Stack‌" memory. – OmG Feb 13 '21 at 16:39
  • Tail recursion doesn't actually call the function, instead it reuses the call-stack frame and just jumps to the start of the function. The stack reuse allows very deep recursion, and a plain jump is more effective than a call. – Some programmer dude Feb 13 '21 at 16:41
  • This is another good answer, specific to the code you wrote and C: https://stackoverflow.com/questions/310974/what-is-tail-call-optimization/9814654#9814654 – Paul Hankin Feb 13 '21 at 16:43
  • @OmG so in the first we are using O(n) memory while in the other O(1)? – Daniel Feb 13 '21 at 18:59

0 Answers0