Callstack not created in recursive function

Question

#include<iostream>
#include<vector>
#include<stack>
#include<utility>
#define P(i, j) all[i-r0][j-c0]
#define C(i, j) check[i-r0][j-c0]

int r0, c0, r1, c1;
std::stack<std::pair<std::pair<int, int>, int>> s;
std::vector<int> mov = {-1, 0, 1};

int move(std::vector<std::vector<bool>> all, std::vector<std::vector<bool>> check){
    auto p = s.top();
    if(p.first.first==r1&&p.first.second==c1)
        return p.second;
    while(!s.empty()){
        for(int i=0; i<3; i++)
            for(int j=0; j<3; j++){
                auto r = p;
                r.first.first += mov[i];
                r.first.second += mov[j];
                r.second++;
                if(r.first.first>=r0&&r.first.first<=r1&&r.first.second>=c0&&r.first.second<=c1&&P(r.first.first, r.first.second)&&!C(r.first.first, r.first.second)){
                    s.push(r);
                    C(r.first.first, r.first.second) = 1;
                    return move(all, check);
                }
            }
        s.pop();
    }
}

int main(){
    std::cin>>r0>>c0>>r1>>c1;
    s.push({{r0, c0}, 0});
    int n;  std::cin>>n;
    std::vector<std::vector<bool>> all(r1-r0+1, std::vector<bool>(c1-c0+1));
    std::vector<std::vector<bool>> check(r1-r0+1, std::vector<bool>(c1-c0+1));
    C(r0, c0)=1;
    for(int i=0; i<n; i++){
        int tempx;
        std::cin>>tempx;
        int tempy1, tempy2;
        std::cin>>tempy1>>tempy2;
        for(int j=tempy1; j<=tempy2; j++)
            if(j<=c1&&j>=c0&&tempx<=r1&&tempx>=r0)
                P(tempx, j) = 1;
    }
    std::cout<<move(all, check)<<'\n';
}

In the above program, when I provide the following inputs

and then use a debugger to analyze the code, its weird that on the 6th call, when the code reaches return move(all, check), its not called and no stack for it is created. Instead its just skipped and s.pop() function is called sequentially. Is there any valid reason for this ?

Please use breakpoints at return move(all, check) and s.pop() if you are putting this on a debugger.

when you have terminal recursion like with `return move(all, check);` the compiler don't need to create a stack frame. because the variable from the calling function can't be used after the call. — Tyker, Jul 11 '18 at 11:21
Your function has undefined behavior because some routes don't return values. — user7860670, Jul 11 '18 at 11:31
It is not valid even if for given input `s.empty()` is false or whatever. — user7860670, Jul 11 '18 at 11:34

Max Langhof · Accepted Answer · 2018-07-11T12:12:32.317

1

Is there any valid reason for this ?

Yes, those reasons are compiler optimizations, specifically tail call optimization. Compilers are allowed to generate whatever code they want as long as the observable behavior of your program doesn't change.

In this case, tail call optimization allows the compiler to eliminate the overhead of creating a new stack frame by just reusing the current one. Since your debugging sessions (and stack frames) are not considered part of observable behavior, it is fully within the compiler's rights to mess with the call stack like this.

A similar thing happens for inlined functions: You also don't get a new stack frame because the function call is replaced with the inlined code.

Most compilers will not do these optimizations in a debug build though. So if you prefer to debug with the "real" call stack, switch to a debug build (and hope that the bug still appears there).

edited Jul 11 '18 at 12:12

answered Jul 11 '18 at 11:37

Max Langhof

23,383
5
39
72

but the observable behaviour is changing. I am not getting the desired output. When the function was supposed to recurse for one final time, its not called instead the next statement is executed – Gaurav Pant Jul 11 '18 at 11:47
@GauravPant this is probably because of undefined behavior – Tyker Jul 11 '18 at 11:49
@Tyker I checked on debugger. The program is reaching the function the 6th time, but its not executed – Gaurav Pant Jul 11 '18 at 11:52
1

@GauravPant if you have undefined behavior anything can happend. – Tyker Jul 11 '18 at 11:56
@Tyker, I know it sounds weird, but after changing the filename, the same code with given inputs works perfectly fine – Gaurav Pant Jul 11 '18 at 12:05
@GauravPant Do you also get this issue in a debug build? The compiler should not do these kinds of optimizations there, so you should be able to, well, debug your problem. The "missing" stack frames are just one of many ways in which debugging optimized code is unintuitive, but is exceedingly unlikely to be the real issue. – Max Langhof Jul 11 '18 at 12:10

Callstack not created in recursive function

1 Answers1