Recursion

Know the rules for writing correct recursive functions (base case, recursive case, etc.).

What value is returned by the call mystery(5);

int mystery(int n)
{
   if (n == 0)
   return 1;
   else
   return 3 * mystery(n - 1);
}

Result: mystery(5): 243

What value is returned by the call recur(27) ;

int recur(int n)
{
   if (n <= 10)
   return n * 2;
   else
   return recur(recur(n / 3));
} 

Result: recur(27): 16

Write a recursive function that computes xn. n is a nonnegative integer.

//x0 = 1.0
//xn = x * xn-1
//for n >= 1
double Power(double x, unsigned int n)
{
    if (n==0) return 1;
    else return x * Power(x, n-1);
}

Write a recursive version of double Power(double x, unsigned int n) that works by breaking n down into halves, squaring Power(x, n/2) , and multiplying by x again if n was odd.

double Power2(double x, unsigned int n)
{
    if (n==0) return 1;
    if (n%2 == 1) return Power(x, n/2) * Power(x, n/2);
    else return Power(x, n/2) * Power(x, n/2) * x;
}

Write a recursive function int Product(int m, int n) which gives the product of the integers in the range m:n (m <= n)

int Product(int m, int n)
{
    if (m==n) return m;
    else return n * Product(m, n-1);
}

Write a recursive function int Min(int A[], int n) to find the smallest integer in the integer array A. n is the number of elements in A.

HINT: you could define an auxiliary function Min2(A,k,j) that finds the smallest integer in A[k:j] and let Min(A,n) = Min2(A,0,n-1)

int Min2(int A[],int k, int j)
{
    if (j == k+1) {
        if (A[k] > A[j]) return A[j];
        else return A[k];
    }
    if (Min2(A, 0, j-1) > A[j]) return A[j];
    else return Min2(A, 0, j-1);
}

int Min(int A[], int n)
{
    return Min2(A, 0, n-1);
}

Inheritance, Polymorphism

1. What will the following program display?

1.line 43のfor loopで

i=0の場合:Person.eat(), Person.speak(), Person.sleep()

i=1の場合:Person.eat(), Student.speak(), Person.sleep()

i=2時:Person.eat(), UCLAStudent.speak(), UCLAStudent.sleep()

Yummy
Hello
ZZZZ
Yummy
I love school
ZZZZ
Yummy
Go Bruins!
ZZZ... CS32 ...ZZZZ

line 49のspは、Studentの対象であるため、Line 51においてStudentである.getReadyForTest()と呼ばれています.つまり、Studentです.study(), Person.sleep()と呼ばれています.

Studying for Midterm test
ZZZZ

line 50のuclapはUCLAStudioの対象であるため、LINE 52ではUCLAStudioである.getReadyForCS 32 Test()と呼ばれています.Student.study(), Person.eat(), UCLAStudent.sleep()は順次sleep()と呼ばれる.

Studying for Midterm test
Yummy
ZZZ... CS32 ...ZZZZ

Result

2. Virtual function?

A virtual function is indicated by including the modifier virtual in the member function declaration (which is given in the definition of the class).
If a function is virtual and a new definition of the function is given in a derived class, then for any object of the derived class, that object will always use the definition of the virtual function that was given in the derived class, even if the virtual function is used indirectly by being invoked in the definition of an inherited function. This method of deciding which definition of a virtual function to use is known as late binding.

3. Pure Virtual Function?

The way to make a member function into a pure virtual function is to mark it as virtual and to add the annotation = 0 to the member function declaration.
Using pure virtual functions means the base version will never be called.
Thus, derived classes must redefine all pure virtual functions so they do something useful.

// examples
virtual double getArea() {return 0;}
virtual void draw( ) = 0;

4. overloading vs redefining

In the C++ literature, a distinction is usually made between the terms redefined and overridden. Both terms refer to changing the definition of the function in a derived class. If the function is a virtual function, this act is called overriding. If the function is not a virtual function, it is called redefining.

5. static binding vs dynamic binding

The technique of waiting until run time to determine the implementation of a procedure is often called late binding or dynamic binding.

6. Should you make a destructor virtual?

It is a good policy to always make destructors virtual.

#include <iostream>
  
using namespace std;
  
class base {
  public:
    base()
    { cout<<"Constructing base \n"; }
    ~base() // --> change to virtual ~base()
    { cout<<"Destructing base \n"; }
};
  
class derived: public base {
  public:
    derived()
    { cout<<"Constructing derived \n"; }
    ~derived() 
    { cout<<"Destructing derived \n"; }
};
  
int main(void)
{
  derived *d = new derived();
  base *b = d;
  delete b;
  getchar();
  return 0;
}

Result is the following:

As we can see in the above output, the base class pointer only removes the base class's destructor without calling the derived class' destructor in the program. Hence, it leaks the memory in the program.