CS210 Lab: Recursion Postlab Answers


Postlab Answers:

Part 1

Use the following function to answer Questions 1 and 2.
int Puzzle (int base, int limit)
{
	if (base > limit)
		return -1;
	else
		if (base == limit)
			return 1;
		else
			return base* Puzzle(base+1, limit);
}
  1. Identify the following:
    1. the base case(s) of the function Puzzle
      1. if (base > limit), return -1;
      2. else if (base == limit), return 1;

    2. the general (recursive) case(s) of the function Puzzle
          if (base < limit), return base* Puzzle(base+1, limit);

  2. Show what would be written by the following calls to the recursive function Puzzle
    1. cout << Puzzle(20,5);
          -1
      because it hits the base case:
      if (base > limit), return -1

    2. cout << Puzzle(3,6);
          60
      because it results in something like the following:
       3 * Puzzle(4,6);
       3 * 4 * Puzzle(5,6);
       3 * 4 * 5 * Puzzle(6,6);
       3 * 4 * 5 * 1

    3. cout << Puzzle(8,8);
          1
      because it hits the base case:
      else if (base == limit), return 1;

Part 2

This question is based on the lab exercise that you just completed.
  1. Another approach to recusively removing 'c' would be to return an address of the next node in sequence (that isn't a c). In this case, you don't have to pass by reference and the prototype will look like the following:
    template < class DT >
    ListNode<DT> * List<DT>:: cRemoveSub ( ListNode<DT> *p )
            
    Write the code to complete this function.
    template < class DT >
    void List<DT>:: cRemove ()
    {
    	head = cRemoveSub(head);
    }
    
    // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
    template < class DT >
    ListNode<DT> * List<DT>:: cRemoveSub ( ListNode<DT> *p )
    {
            ListNode<DT> *q;   // Temporary pointer
    
            if (p!=0)
            {
                    p->next=cRemoveSub(p->next);
                    if (p->dataItem=='c')
                    {
                            q=p;
                            p=p->next;
                            delete q;
    
                    }
                    return p;
            }
    
    } 
    

Back to Exercise click here
Back to Recursion Lab click here

CS Dept Home Page
CS Dept Class Files
CS210 Class Files

Copyright: Department of Computer Science, University of Regina.