# Exiting Recursive Function C++ [closed]

In the following function IsDoubleString(),if res is true then it shouldn't call IsDoubleString(), I debugged the code but I am unable to understand that once it hit the line returns res; why does the control go inside the if(!res) condition? Shouldn't it be directly returning the res value to the main function?

``````bool IsDoubleString(map<char,int> Word)
{
bool res = true;
for (auto itr = Word.begin(); itr != Word.end(); ++itr)
{
if (itr->second % 2 != 0)
{
itr->second -= 1;
res = false;
break;
}
}
if (!res)
{
IsDoubleString(Word);
}
//return res; should directly return the value to main() but while
//debugging I
//found it goes inside the if(!res) above this return res; line
return res;
}

int main()
{
map<char, int> WordMap;
WordMap.insert({ 'w', 2 });
WordMap.insert({ 'o', 1 });
IsDoubleString(WordMap) ? cout << "Yes" << endl : cout << "No" << endl;
return 0;
}

/*The code aims to print Yes or No if from the given string we can divide the string symmetrically, Entered string is P, A+B = P and A=B Print Yes and if we can't divide the string such A is not equal to B we will delete the characters so that we wilL try to make A equal to B
1. wow - Yes, we have to delete o, then A = B = w; P =A+B
2. lala - Yes A = B = la; P = A+B
3. a - No, since we can divide a string of size 1
4. ab - No, if A=a,B=b; A!=B or viceversa
So, the following code works in such a way , We entering a string which is being entered in WordMap, in this scenario we are entering wow string which is inserted in the WordMap and it works perfectly but as soon it returns res; the control goes inside if(!res) but this shouldn't happen as res is true*/
``````

`main` called `IsDoubleString`, then `IsDoubleString` called `IsDoubleString`. When `IsDoubleString` returns, it returns to `IsDoubleString` because `IsDoubleString` called `IsDoubleString`. In fact `IsDoubleString` will return to `IsDoubleString` as many times as `IsDoubleString` called `IsDoubleString`... then `IsDoubleString` returns to `main`.

That is probably confusing. So let us talk about the call stack.

When you do a call, the program needs to return to where it was called. Now, before you quote on me on that and tell that that is why you are asking, please keep reading.

If the function `A` calls the function `B`, and then the function `B` calls the function `C`... the runtime needs to remember all that, so that `C` returns to `B` and `B` returns to `A`. That means that the runtime cannot simply store where to return into a variable... it need some sort of data structure that grows.

What kind of data structure? Well, let us see... the first item it has to retrieve is the last item added. So it is LIFO. The runtime needs a stack.

What happens when `A` calls `B`, and then `B` calls `B`. Well, first when `A` calls `B`, the location in `A` to return is pushed to the stack, and then when `B` calls `B` the location in `B` to return is pushed to the stack. That means that the stack now contains a position in `A` and then a position in `B`.

When returning, it takes first the last, which is the position in `B`. So `B` returns to `B`. And then it takes the position in `A`, so `B` returns to `A`.

I am ingoring a lot about calling conventions. I would be burn at the stake if I do not mention that this is an oversimplification of calling convetions.

Ok, that might still be confusing. Let us try again...

1. `A` calls `B`, the position in `A` is pushed to the stack:

``````Stack: {..., `A`}
``````
2. `B` calls `B`, the position in `B` is pushed to the stack:

``````Stack: {..., `A`, `B`}
``````
3. `B` returns, the position in `B` is popped from the stack:

``````Stack: {..., `A`}
``````
4. `B` returns again, the position in `A` is popped from the stack:

``````Stack: {...}
``````

Let us see what happens if `B` called itself twice:

1. `A` calls `B`, the position in `A` is pushed to the stack:

``````Stack: {..., `A`}
``````
2. `B` calls `B`, the position in `B` is pushed to the stack:

``````Stack: {..., `A`, `B`}
``````
3. `B` calls `B`, the position in `B` is pushed to the stack:

``````Stack: {..., `A`, `B`, `B`}
``````
4. `B` returns, the position in `B` is popped from the stack:

``````Stack: {..., `A`, `B`}
``````
5. `B` returns, the position in `B` is popped from the stack:

``````Stack: {..., `A`}
``````
6. `B` returns again, the position in `A` is popped from the stack:

``````Stack: {...}
``````

We observe that when `B` called itself twice, `B` was pushed to the stack twice, and as a result, `B` returned to `B` twice.

For abstract, in a recursive function (one that calls itself), it makes sense that it will return to itself. After all, when you do a call, the program needs to return to where it was called. Now, you can quote me on that. Once it has returned to itself as many times as it called itself, then it can return to the original caller.

With that in mind,

`main` called `IsDoubleString`, then `IsDoubleString` called `IsDoubleString`. When `IsDoubleString` returns, it returns to `IsDoubleString` because `IsDoubleString` called `IsDoubleString`. In fact `IsDoubleString` will return to `IsDoubleString` as many times as `IsDoubleString` called `IsDoubleString`... then `IsDoubleString` returns to `main`.

• @DebabrataPonda perhaps you would enjoy an explanation of the Stack from Professor David Brailsford his explanation is both much more didactic and more complete than mine (edit: I did not mention returned values) - Fun fact: the name of the sister site Stack Overflow refers to the error that happens when a call excedes the maximun size of the call stack. – Theraot Jul 7 '19 at 7:51