Lab 04 – Recursive Lists

Student Information

• Kevin Rodriguez
• Student ID: 008858727
• Course: CS 315 – Data Structures (Fall 2025)
• Lab: Lab 04 – Recursive Lists
• **Repository Link: ** https://github.com/Pwingles/recursiveList.git

---

Collaboration & Sources

This project was completed collaboratively by the group members

• Will Meyer

• Caleb Clements

• We worked together to design and implement recursive solutions in C++.

• No outside code was copied.

---

Implementation Details

The lab required solving recursive-list problems in solutions.cpp, building on the provided reclists.hpp:

1. numNodesAtTheTopLevel
   Counts nodes at the top level of a list by recursively traversing with cdr.

2. numAtomsAtTheTopLevel
   Counts atoms at the top level of a recursive list using car/cdr recursion and atom checks.

3. find
   Checks if a given atom q exists inside a list p. Implemented recursively with car/cdr.

4. areEqual
   Determines whether two lists of atoms are identical in order and content. Recursively compares car(p) and car(q).

5. evenNumberOfAtoms
   Determines if a list has an even number of atoms. Implemented by skipping two nodes per recursive call (cdr(cdr(p))).

6. everyOtherAtom
   Checks whether the i-th atom of p appears at the 2i-th position of q.

   • Base case: p empty → true.
   • Guard: q must have at least two elements.
   • Compare car(p) with car(cdr(q)).
   • Recursive step: call on cdr(p) and cdr(cdr(q)).

---

Testing & Status

We tested each function using the provided CLion driver (main.cpp) with various recursive lists.

Sample Tests

Function	Input	Expected Output
numNodesAtTheTopLevel	(((a b) c) d (a b))	3
numAtomsAtTheTopLevel	(((a b) c) d (a b))	1
find	(a b c d), q = c	true
areEqual	(a b c d), (a b c d)	true
areEqual	(a b c d), (b a c d)	false
evenNumberOfAtoms	(a b c d e f g h i j)	true
evenNumberOfAtoms	(a b c d e)	false
everyOtherAtom	p = (a), q = (b a)	true
everyOtherAtom	p = (a b c), q = (a a c b a c e a)	true
everyOtherAtom	p = (a b), q = (a c d b)	false

Status

• All required functions compile and run correctly.
• Tested with multiple valid and edge-case inputs.
• No runtime errors after proper null checks.