Please, what is the logic behind this recursive function call?

[ayoesquire]

It is a solution to an assessment which I viewed only after I had attempted the exercise to the best of my abilities for about a week. It's from the text "Beginning Visual C++" by Ivor Horton pg 476. http://www.wrox.com/WileyCDA/WroxTitle/Ivor-Horton-s-Beginning-Visual-C-2013.productCd-1118845714.html

I want to know how the function void listNode() somehow displays an output (i.e. line 7 cout << setw(12) << value;) even after the if statement has been satisfied for the pointer argument m_pLeft.

This is because, it seems to me that the member selection operator m_pLeft->listNode(); calls the function listNode() again, hence invokes a recursion which should lead to an indefinite loop. But it appears this is not the case.

I know the solution is correct but I need to understand what's going on here. I could have overlooked this and moved on but that will be no proper way to learn.

Please your explanations and suggestions will be well appreciated.

Thanks!

  void listNode()
    {

      if (m_pLeft)                     // If there's a left node
        m_pLeft->listNode();           // Output its value

      cout << setw(12) << value;       // Output the current node value
      if (++listCount % 5 == 0)
        cout << endl;

      if (m_pRight)                    // If there's a right node
        m_pRight->listNode();          // Output its value
    }

    int value{};                       // Value of the node
    CNode* m_pLeft{};                  // Pointer to left node
    CNode* m_pRight{};                 // Pointer to right node
    static int listCount;              // Count of number of output values
  };

[Repeater]

This is because, it seems to me that the member selection operator m_pLeft->listNode(); calls the function listNode() again, hence invokes a recursion which should lead to an indefinite loop.

It calls the function on a different node. Eventually, the function is called on a node which does NOT call the function again (because it has no left child and no right child), and the recursion backs up a step to the parent node. Eventually, the function has been called on every node.

[icy1]

Hi ayoesquire, it'd also help clarify if you posted a more complete, compiling example. In this case one could piece it together from the context. In particular, the mysterious line 0 could be class Node { , and it wouldn't hurt to have an example of the caller in a short int main() or so. The indentation was a little off, so I had to double-take to realize that lines 15-18 were not part of the function.

[ayoesquire]

Thank you @Repeater and @icy1

@Repeater:
Thanks for the insight. If I understand you correctly, it means the code implements a backward recursion. What I'm yet to understand is how the following lines:

cout << setw(12) << value;       // Output the current node value
if (++listCount % 5 == 0)
    cout << endl;

fits into the rest of the listNode() function code. Is it that it displays a value only when the if condition returns false?
Thank you.

@icy1:
Thanks for showing interest and sorry for the omission. The reason I refrained from posting the entire code initially was because it seemed a bit lengthy to me. However, here's the question and solution code in full:

A binary tree is a structure made up of nodes, where each node contains a pointer to a “left”
node and a pointer to a “right” node plus a data item, as shown in Figure 9-6.
The tree starts with a root node, and this is the starting point for accessing the nodes in
the tree. Either or both pointers in a node can be nullptr. Figure 9-6 shows an ordered
binary tree, which is a tree organized so that the value of each node is always greater than or
equal to the left node and less than or equal to the right node.

Define a class that defines an ordered binary tree that stores integer values. You also need to
define a Node class, but that can be an inner class to the BinaryTree class. Write a program to
test the operation of your BinaryTree class by storing an arbitrary sequence of integers in it
and retrieving and outputting them in ascending sequence.
Hint: Don’t be afraid to use recursion.

Culled from "Beginning Visual C++" by Ivor Horton pg 476. http://www.wrox.com/WileyCDA/WroxTitle/Ivor-Horton-s-Beginning-Visual-C-2013.productCd-1118845714.html

// Soln 9_04.cpp
// The rand_s() function generates random integers from 0 to UINT_MAX
// To use rand_s function you must first define _CRT_RAND_S

#define _CRT_RAND_S             // For secure random number generator
#include <iostream>
#include <iomanip>
#include <cstdlib>              // For rand_s function

using std::cout;
using std::endl;
using std::setw;

class CBinaryTree
{
private:
  class CNode
  {
  public:
    // Node constructor
    CNode(int n) : value{ n } {}

    // List the node values in order
    void listNode()
    {

      if (m_pLeft)                     // If there's a left node
        m_pLeft->listNode();           // Output its value

      cout << setw(12) << value;       // Output the current node value
      if (++listCount % 5 == 0)
        cout << endl;

      if (m_pRight)                    // If there's a right node
        m_pRight->listNode();          // Output its value
    }

    int value{};                       // Value of the node
    CNode* m_pLeft{};                  // Pointer to left node
    CNode* m_pRight{};                 // Pointer to right node
    static int listCount;              // Count of number of output values
  };

public:
  CBinaryTree() = default;
  void add(int n);                     // Adds a value to the tree
  void add(int n, CNode* pNode);       // Adds n relative to pNode node

  // List the nodes in sequences
  void listNodes()
  {
    CNode::listCount = 0;
    if (!m_pRoot)
      cout << "Binary tree is empty." << endl;
    else
      m_pRoot->listNode();
  }

private:
  CNode* m_pRoot{};                    // Pointer to the roor node
};

int CBinaryTree::CNode::listCount{};   // Initialize static member

// Add a value to the tree
void CBinaryTree::add(int n)
{
  if (!m_pRoot)                        // If there's no root node
    m_pRoot = new CNode(n);            // the new node is the root
  else                                 // otherwise
    add(n, m_pRoot);                   // add the node (recursive)
}

// Add a value relative to a given node
void CBinaryTree::add(int n, CNode* pNode)
{
  if (n == pNode->value)               // If value equals current node
  { // Always add equal values as left node
    CNode* pNewNode = new CNode(n);    // Create the new node for the value
    CNode* pTemp = pNode->m_pLeft;     // Save left ptr for current node
    pNode->m_pLeft = pNewNode;         // then make it point to new node
    pNewNode->m_pLeft = pTemp;         // Left ptr for new node point to old left node
  }
  else if (n > pNode->value)           // If new value is greater than right node value
  {                                    // it must go to the right
    if (!pNode->m_pRight)              // so if there's no right node
      pNode->m_pRight = new CNode(n);  // make the new node the right node
    else                               // Otherwise
      add(n, pNode->m_pRight);         // add it relative to right node(recursive)
  }
  else                                 // New number is less than current node value
  {
    if (!pNode->m_pLeft)               // so if there's no left node
      pNode->m_pLeft = new CNode(n);   // make the new node the left node
    else                               // Otherwise
      add(n, pNode->m_pLeft);          // add it relative to the left node(recursive)
  }
}


int main()
{
  CBinaryTree tree;                    // Create a binary tree
  unsigned int number{};               // Stores a number to be added to the tree

  cout << "Random values inserted in the tree are:" << endl;

  // Add 100 random number to the tree in the range from 1 to 1,000,000
  double max{ 1000000.0 };
  for (int i{}; i < 100; ++i)
  {
    if (rand_s(&number) != 0)
      cout << "Random number generator failed!" << endl;

    // Change the range from (0 to UINTMAX) to (1 to max)
    number = static_cast<unsigned int>((static_cast<double>(number) / UINT_MAX)*max) + 1;

    tree.add(number);
    cout << setw(12) << number;
    if ((i + 1) % 5 == 0)
      cout << endl;
  }
  cout << endl << "Output from the tree is:" << endl;
  tree.listNodes();
}

[icy1]

Ok, this is a good start; just needed a few minor tweaks to the randoms and CRT stuff to be runnable online. One thing to note is that the manager creates nodes (new) and never destroys them (delete) . Perhaps a good next step would be to implement a recursive CleanUp() function, similar to the listNodes(), going left as far as possible, but this time going (destroying) right before dealing with itself. CBinaryTree destructor can call this function. Can make it public and call it from main().

how does listNode() work?
- it prints all left-most values first, starting with, visually, the bottom left of the tree
- then it prints current value
- then it prints right value
- these are in ascending order because of add()

add() logic:
1. values equal to current node value cause a new value to be inserted between current node and left branch as the new left node
2. values not equal to current node -- walk down, left if less, right if greater, until there is a logical opening (missing desired left/right). If any equal values during the walk, #1 is performed. Otherwise it'll create the desired left/right node.

It's an ordered tree in that everything left of Root is less than or equal to Root, and everything right of Root is greater than Root. Root could be anything and is always the first value inserted into the tree; this value is never changed. There's no guarantee of a left side or a right side, and visually the depth of the tree could be much greater than seemingly needed -- perhaps an imbalanced tree.

[ayoesquire]

@icy1: wow thanks. I am beginning to understand this. I will take sometime to look at the code again till I think am comfortable with it.

Thank you for your time! So grateful.