Recursive boolean function

Good day everyone

In preparation for examination I am going through some recursion exercises. Just when I thought that I was getting the hang of it, I came across one that has me stumped! The question is to write a recursive boolean function that compares two stacks and returns true if they are identical. This is where I get stuck:
If the top items of both stacks are the same, the recursive call always returns true, because 'true' is saved on top of the return stack.
Your help will be much appreciated!

Here is my code:
template<class Type>
bool identicals(stackType<Type> s1, stackType<Type> s2)
{
if(!s1.isEmptyStack() && !s2.isEmptyStack())
{
if(s1.top() != s2.top())
return false;
else
{
s1.pop();
s2.pop();
return true;
identicals(s1, s2);
}
}
}
Last edited on
You are returning true before you compare the next one down. You just need to put in a test if the stack is now empty and then otherwise recurse, like so:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// pseudocode, based off assuming you are using std::stack
template <typename StackType>
bool identical(StackType s1, StackType s2) {
    if (s1.empty() && s2.empty())
        return true;  // the stacks are both empty, therefore they are the same

    if (s1.empty() || s2.empty())
        return false; // one of the stacks is empty but the other isn't - different

    if (s1.top() != s2.top())
        return false; // the values are different

    // remove the top elements
    s1.pop();
    s2.pop();

    // return the result with the next layer of the stack
    return identical(s1, s2);
}
Last edited on
Awesome solution, thank you. Works perfectly.
Last edited on
Topic archived. No new replies allowed.