Search code examples
c++recursionlifo

How recursion uses stack data structure?

I had read recently that recursion uses system stack for storing return addresses of function calls. So, I just made a random code to understand this LIFO concept in recursion 

int fun( int x) 
  {  if ( x<6 || x>6 ) 
       { cout<<x; 
          return 0; 
        } 
      else 
       return max(fun(x-1),fun(x+1)); 
    } 
    int main(){ 
     cout<<fun(6); 
     return 0; 
  }

I expect output

570

Actual output is

750

I was assuming function will call in this order-

fun(6)->fun(5) { it will print 5 then return 0} ->fun(7) { it print 7 then return 0} -> max(0,0) { return 0}

Correct me, where I am getting wrong.

Solution

  • In C++, the order of evaluation of arguments is unspecified.

    When writing max(fun(x-1),fun(x+1)); the compiler is free to choose to evaluate fun(x+1) first.