How to use function members of a class recursively?

Question

How can you define a function of a class to be recursive?, this is what I have been doing:

class A
{
 private:
  
 public:
  _recursive(A *var);
  recursive()
}

A::recursive()
{
  _recursive(this)
}

A::_recursive(A *var)
{
  _recursive(var->next);
}

And on main:

A *temp = new A();
A->recursive();

I have also tried (same class as before)

A *temp = new A();
A->_recursive(&A);

There seems like this should be something somebody else has found and easier or more elegant way of doing so, I tried making the class simple just to demonstrate, but this is a single linked list transverse program so it needs recursion.

_"... but this is a single linked list transverse program so it needs recursion."_ Not really. — πάντα ῥεῖ, Mar 21 '22 at 08:28
it is unclear why you think you need to pass `this` explicitly. Actually your confusion is not related to recursion. `_recursive` already has access to `this` you need not pass it again. — 463035818_is_not_an_ai, Mar 21 '22 at 08:32
`void A::do_something() { if (next) next->do_something(); }`? — molbdnilo, Mar 21 '22 at 08:34
maybe you removed too much from your example such that the actual problem you encountered is not present anymore. I suggest to go back to the real code and try to create a [mcve] that includes the actual issue — 463035818_is_not_an_ai, Mar 21 '22 at 08:36
Your function `recursive()` is not recursive (not withstanding the name) but simply calls `_recursive()`. `_recursive()` calls itself so is, by definition, recursive. The problem is that `_recursive()` unconditionally calls itself, so never returns, and is infinitely recursive (i.e. it keeps calling itself and never returns). You need to change its logic to something akin to `A::_recursive(A *var) {if (some_condition()) _recursive(var->next);}` where `some_condition()` will be `false` - preferably after a finite number of recursive calls. — Peter, Mar 21 '22 at 08:47

score 2 · Answer 1 · answered Mar 21 '22 at 08:47

Front-ending a recursive algorithm that, by its normative nature uses a parameterized gating is what I think you're actually trying to ask about. For a linked list, for example, given this procedural typical recursive solution where the descent is parameterized and the base-case is exit-on-null:

struct Node
{
    int data;
    Node *next;
};

void print_list(Node *p)
{
    if (!p)
        return;

    std::cout << p->data << ' ';
    print_list(p->next);
}

You can do the same thing with a member function by throwing that base logic in as a condition of the recursion. For example:

struct Node
{
    Node *next;
    int data;
    
    void print()
    {
        std::cout << data << ' ';
        if (next)
        {
            next->print();
        }
    }
};

The same modus-operandi can be extended to more complex structures like a BST node:

struct BSTNode
{
    BSTNode *left;
    BSTNode *right;
    int data;
    
    void inorder()
    {
        if (left)
            left->inorder();

        std::cout << data << ' ';

        if (right)
            right->inorder();
    }
};

At least I think that's what you're asking about.

Remy Lebeau · Answer 2 · 2022-03-21T09:48:13.807

this is a single linked list transverse program so it needs recursion.

You don't actually need a recursive loop at all. An iterative loop will suffice, and be safer for long lists as you won't run the risk of a stack overflow pushing each recursive call into the call stack (if you write the loop to use tail-call recursion, any decent compiler should be able to apply tail-call optimization to convert the recursive loop into an iterative loop), eg:

class A
{
 public:
  A *next;
  void doSomething();
}

A::doSomething()
{
  A* var = this;
  do {
    // do something with var...
    var = var->next;
  }
  while (var);
}

How to use function members of a class recursively?

2 Answers2