1
h06
CS24 S17
Name:
(as it would appear on official course roster)
Umail address: @umail.ucsb.edu section
Optional: name you wish to be called
if different from name above.
Optional: name of "homework buddy"
(leaving this blank signifies "I worked alone"

h06: Chapter 9: Recursive Thinking

ready? assigned due points
true Wed 05/24 05:00PM Fri 06/09 01:00PM

You may collaborate on this homework with AT MOST one person, an optional "homework buddy".

MAY ONLY BE TURNED IN IN THE LECTURE/LAB LISTED ABOVE AS THE DUE DATE,
OR IF APPLICABLE, SUBMITTED ON GRADESCOPE. There is NO MAKEUP for missed assignments;
in place of that, we drop the three lowest scores (if you have zeros, those are the three lowest scores.)

Please:

  • No Staples.
  • No Paperclips.
  • No folded down corners.

Complete your reading of Chapter 9 (If you don’t have a copy of the textbook yet, there is one on reserve at the library under “COMP000-STAFF - Permanent Reserve”).

    1. (10 pts) Write a recursive function to check if an input string is a palindrome. Decide on the parameters and return type of the function as appropriate.
    2. (10 pts) Consider the following definition of a doubly linked-list. 
    class LinkedList{
	public:
		LinkedList():head(0), tail(0){}
		~LinkedList();
		void reverse(); //reverses the order of elements in the linked list 
		void insert(int value);
	private:
	    struct Node{
  			int data;
  			Node* next;
  			Node* prev;
		};
		Node* head;
		Node* tail;
		//Add your helper function here that recursively reverses the order of elements in the linked list

		
};
    Write the definition of a helper function in the provate section of the class provided above that recursively reverses the order of elements in the linked list. This function will be used by the reverse() method. The implementation of the function should be provided on the next page.
    3. (10 pts) Consider the doubly linked list in the previous question. Implement the reverse method that uses a helper function to recursively reverse the order of elements in a linked list. You must implement the helper function as well.
    4. (5 pts) Write a recursive function that finds the sum of the first 'n' odd positive integers. Find a variant expression and a threshold for this function.