Tail Recursion(If the Recursion call is the Last thing done by the function)
in Cpp with 0 comment

Tail Recursion(If the Recursion call is the Last thing done by the function)

in Cpp with 0 comment

Tail Recursion

If the Recursion call is the Last thing done by the function!
Remember, it's the last thing!!!last thing!!!last thing!!!
At this point we have no need to keep record the previous state, we just jump to the entry with the current state we need. So the space complexity will be O(1).

Some example:

//calculate the sum from 1 to n

//Recursive
int calculate1(int n)
{
    if(n==1)return n;
    else return n+calculate1(n-1);
}

//iterate
int calculate2(int n)
{
    int sum=0;
    for(int i=1;i<=n;++i)sum+=i;
    return sum;
}

//Tail Recursive
calculate3(int n,int curSum)
{
   if(n==0)return curSum;
   else return calculate3(n-1,curSum+n);
}

Some understanding

The tail recursive need more parameters than the linear recursive. The normal recursive will not keep record the current result but the tail recursive will save the result have calculated then pass it to the next call(it self).

// TO DO
// TO DO

Responses