DEV Community

Debjoty Mitra
Debjoty Mitra

Posted on • Updated on

Tail Recursion

If in a recursive function, the recursive call is the last statement of the function, then it is called a Tail Recursion. In returning time, it doesnโ€™t have to perform anything at all.

void fun(int n){
    if(n>0){
        cout<<n<<endl;
        fun(n-1);
    }
}
Enter fullscreen mode Exit fullscreen mode

Same code using a loop:

void fun(int n){
    while(n>0){
        cout<<n<<endl;
        n--;
    }
}
Enter fullscreen mode Exit fullscreen mode

To conclude, the time complexity of both codes is the same. But in recursive calls, as it uses stacks, it is actually taking extra space. So, the space complexity for the loop is O(1), but for the tail recursion, it is O(n). So, it is better to use a loop if it is a tail recursion.

Top comments (0)