Summary
Most everything that can be done with a loop can be done with a recursion (and, to some extent, vice versa). Some things, however, are best done with recursion, given the constraints of the problem given. Here, we explore a common concept of String reversal from a different perspective, comparing iterative vs. recursive approaches.
Skills Expected
Linked Structures
Recursion
Big-O Notation
Assignment Description
Create a simple singly-linked list (no previous, no tail pointers) where each node contains a word. Create a “reverse print” function that prints out the very last node first and then all the way back to the beginning. Do not use String concatenations or another structure to store the Strings to print out. Print each node in its own line.
For example, if the list contains:
“Hello” - “There” - “How” - “Are” - “You?”
It will print:
“You?”
“Are”
“How”
“There”
“Hello”
Grading Criteria
Implementation
[2 Points] Singly-Linked Structure
[3 Points] Copy constructor (deep copy)
[3 Points] Reverse print function (iteration)
[5 Points] Reverse print function (recursion)
Demonstration
[1 Point] singly-linked list structure with at least 10 nodes
[1 Point] Iterative solution demonstration
[1 Point] Recursive solution demonstration
[1 Point] Copy constructor demonstration
Big-O Analysis
[1 Point] Copy constructor
[1 Point] Iterative solution
[1 Point] Recursive solution
