Recursion and Additional Scalar Types

Tom Kelliher, CS17

Apr. 29, 1996

Professor Levish enlightens us on the nature of the existential semicolon in the while and do/ while constructs.

We will discuss arrays and files on Friday.

We'll also have a surprise quiz on Friday.

Recursion

A recursive function:

Any function which calls itself, directly or indirectly, is called a recursive function.

What prevents a recursive function from infinitely recursing?

Requirements for recursion:

1. Decomposition into smaller problems of same type.
2. Recursive calls must diminish problem size.
3. Necessity of base case.
4. Base case must be reached.

Example: Printing Integers from 1 to n

void print(int n)
{
   if (n > 0)
   {
      print(n - 1);
      cout << n;
   }
}

Does it meet the requirements?

What happens if we swap the statements in the if block?

How does this work?

Example: Factorial

int fact(int n)
{
   assert (n >= 0);   // Use assert.h.

   if (n < 2)
      return 1;
   else
      return n * fact(n - 1);
}

Does it meet the requirements?

How does this work?

Additional Scalar Types

Integer Types

1. char.
2. short int or short.
3. int.
4. long int or long.
5. signed, unsigned.

Ranges, defaults for signed, unsigned?

Float Types

1. float
2. double
3. long double

Ranges, precisions? ((6, 38), (19, 4,932)).

Arithmetic Anomalies

• Division by zero.
• Integer division vs. float division.
• Arithmetic overflow.
• Arithmetic underflow.
• Representational errors.
• Cancellation errors.

Arithmetic Conversions

• Implicit (operator, assignment, return, some parameters), Explicit (casts).
• From smaller to larger --- ``safe.''
• From larger to smaller --- ``unsafe.''