[RESOLVED] recursive function logic.

I have 2+ Mobs, with the ability to follow eachother. When following, movement is controlled by the leader. The issue I was having was that the initial leader would end up following one of its followers, stopping all along the chain from moving.

To counteract this I passed a quick check

Code:

---

if(leader != this)
{
    follow();
}

---

The next issue was when A follows B who follows C who follows A. My check did not cover that.
a->b->c->a

The below code sends "this" as the argument L. It SHOULD check each Mob, see if it has a leader, check if that leader is me and if it isnt me check its leader and so forth.

There are no syntax errors (that my compiler tells me about), so it must be a logic problem.

Hopefully this snippet is quite easy to follow (for at least 1/2 recursions) and any logic problem should be obvious to everyone except me...because that happens some times :(

Code:

---

bool Mob::checkLeader(Mob* L)
{
    if(leader != NULL)          //leader exists
    {
        if(leader != L)        //leader is not me
        {
            if(checkLeader(L))  //leaders-leader(recursive, follow line of leaders to the end)
            {
                return true;
            }
            return false;
        }
        return true;
    }
    return false;
};

---

Thanks for any help in advance and please feel free to suggest any other method you prefer .

Code:

---

bool Mob::checkLeader(Mob* L)
{
    if(leader != NULL)        //leader exists
    {
        if(leader != L)        //leader is not me
        {
            if(checkLeader(L))  //leaders-leader(recursive, follow line of leaders to the end)
            {
                return true;
            }
            return false;
        }
        return true;
    }
    return false;
};

---

According to your logic, if leader == NULL, you return false. Was this intended ? I guess you meant the leader has it's "leader" data member pointing to itself, right ? if so, did you remember to update it as so ?

Also:

Code:

---

          if(checkLeader(L))

---

For this to be recursive, you probably should have checked:

Code:

---

    if (leader->checkLeader(L))

---

Two last note about style - if a function/method returns a bool value, there is no point in checking:

Code:

---

if (f()) {
    return true;
}
return false;

---

You could simplify to this:

Code:

---

  return f();

---

And another thing - you could shorten the method to a single row by using logic && and || operators. You could count on the "short-circuiting" properties of the logic operators and, assuming that the leader's "leader" member is pointing to itself, you could simply do this:

Code:

---

bool Mob::checkLeader(Mob* L)
{
    return (leader == L || (leader != NULL && leader->checkLeader(L));
};

---

I hope this helps.

Regards,
Zachm

The function you posted suffers from an infinite recursion: If leader is neither equal to NULL nor to the L that got passed, the function reaches the innermost if and calls itself passing the same L and changing nothing else either. And that goes on and on and...

I'm tempted to even say that, strictly speaking, this isn't even recursion because there's no change between two nested calls except eating up stack space.

I can't really follow the logic of your code basd on the information I have, but maybe something like

Code:

---

            if(checkLeader(L->leader))  //leaders-leader(recursive, follow line of leaders to the end)
            {
                return true;
            }
            return false;

---

would come closer to what you want?

HTH

Hey guys, just woke up from a little sleep so my ability to follow logic is slightly impaired :D

I'm not sure if i mentioned this, but checkLeader is being called on a potential leader of "this", checking the potential leaders leader, not this.leader .

"According to your logic, if leader == NULL, you return false. Was this intended ? I guess you meant the leader has it's "leader" data member pointing to itself, right ? if so, did you remember to update it as so ?"
Yes, the function returns TRUE if "this" is the leader, and false on any other outcome (no leader, leader != me).

this check if (leader->checkLeader(L)) was what I meant to add :) it helped get one step closer. I was also calling this.checkLeader, not this(potential leader).checkLeader, but that was further back in the code, before this snippet.

return (leader == L || (leader != NULL && leader->checkLeader(L));
I considered shortening this when first writing it, but without the initial long way I would have lost track of what I was typing :) but that would return what I wanted, thanks for shortening it for me.

@Eri523, leader will always be this, !this or carry on along a line of finite Mob's until it reaches a NULL leader, passing false back through each iteration back to the original caller.
checkLeader(L->leader)) isn't checking for THIS (original caller) which is what i need, as every Mob check this before actually acquiring a leader.

This seems to have solved my initial problem. Now that I know the logic is right, I can tackle the next bug that has appeared :D probably something in my movement code. thanks guys, you've been very helpful.