Recursion Primer using C++: Part 3

// Runtime Structured Nested Recursion	

#include <iostream>

// Node for Inner Link List 
struct Node 
{ 
	int iData; 
	Node* pNextNode; 

	Node() 
	{ 
		iData = 0; 
		pNextNode = NULL; 
	} 
};

// Node for Nested Link List 
struct NestedNode 
{ 
	int iData; 
	Node* pHead; 
	NestedNode* pNextList; 
	
	NestedNode() 
	{ 
		iData = 0; 
		pHead = NULL; 
		pNextList = NULL; 
	} 
};

// Add element in the outer link list 
NestedNode* AddNestedList(NestedNode* pHead, int iData) 
{ 
	if (pHead == NULL) 
		return NULL; 
	
	if (pHead->pNextList == NULL) 
	{ 
		pHead->pNextList = new NestedNode(); 
		pHead->iData = iData; 
		return pHead; 
	} 
	else 
	{ 
		NestedNode* pTemp = pHead->pNextList; 
		
		while (pTemp != NULL) 
		{ 
			pTemp = pTemp->pNextList; 
		} 
		
		pTemp = new NestedNode(); 
		pTemp->iData = iData;
		pTemp->pNextList = pHead; 
		pHead = pTemp; return pHead; 
	} 
}

// Add element in the inner link list 
void AddNestedItem(Node** pHead, int iData) 
{ 
	if (*pHead == NULL) 
	{ 
		*pHead = new Node(); 
		(*pHead)->iData = iData; 
	} 
	else 
	{ 
		Node* pTemp = (*pHead)->pNextNode; 
		
		while (pTemp != NULL) 
		{ 
			pTemp = pTemp->pNextNode; 
		} 
		
		pTemp = new Node(); 
		pTemp->iData = iData; 
		pTemp->pNextNode = *pHead; 
		*pHead = pTemp; 
	} 
}

// Print the inner link list 
void PrintNestedList(Node* pHead) 
{ 
	if (pHead != NULL) 
	{ 
		std::cout << " -> " << pHead->iData << std::endl; 
		PrintNestedList(pHead->pNextNode); 
	} 
	else 
		return; 
}

// Print the outer link list 
void TraverseNode(NestedNode* pHead) 
{ 
	if (pHead == NULL) 
		return; 
	else 
	{ 
		std::cout << pHead->iData << std::endl; 
		PrintNestedList(pHead->pHead); 
		TraverseNode(pHead->pNextList); 
	} 
}

int main()
{
	// Header of Nested Link List
	NestedNode* pNested = new NestedNode();

	// First Nested Link List store items multiple of 2
	pNested = AddNestedList(pNested, 2);
	AddNestedItem(&pNested->pHead, 4);
	AddNestedItem(&pNested->pHead, 14);
	AddNestedItem(&pNested->pHead, 20);
	AddNestedItem(&pNested->pHead, 36);

	// Second Nested Link List store items multiple of 3
	pNested = AddNestedList(pNested, 3);
	AddNestedItem(&pNested->pHead, 9);
	AddNestedItem(&pNested->pHead, 21);
	AddNestedItem(&pNested->pHead, 27);	

	// Third Nested Link List store items multiple of 5
	pNested = AddNestedList(pNested, 5);
	AddNestedItem(&pNested->pHead, 25);
	AddNestedItem(&pNested->pHead, 45);
	AddNestedItem(&pNested->pHead, 50);
	AddNestedItem(&pNested->pHead, 70);
	AddNestedItem(&pNested->pHead, 85);
	AddNestedItem(&pNested->pHead, 95);

	// Traverse Nested Link Recursively
	// Every items itself is Link List
	// Traverse that Link List Recursively too
	// to print all items in Nested Link List
	// Recursive function call another recursive function
	TraverseNode(pNested);
}