Reference Parameters and Recursion

Tom Kelliher, CS17

Apr. 29, 1996

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

Schedule for remainder of semester:

Reference Variables and Parameters

Reference Variables

An alias, synonym, or just another name for a variable previously declared.

Example:

int i = 0;
int& j = i;   // j is a reference to i;

cout << setw(8) << i << setw(8) << j << endl;
i = 5;
cout << setw(8) << i << setw(8) << j << endl;
j = 10;
cout << setw(8) << i << setw(8) << j << endl;
cout << &i << "   " << &j << endl;

Notes:

What good is this?

Reference Parameters

Suppose a formal parameter was declared as a reference variable:

void f(int& i);
void g(int i);
void h(void);

void h(void)
{
   int a = 12;

   f(a);
   cout << a << endl;
   g(a);
   cout << a << endl;
}

void f(int& i)
{
   i = 0;
}

void g(int i)
{
   i = 20;
}

Does this restrict what we can use as actual parameters?

Notes:

Example:

void add(int& sum, int a, int b)
{
   sum = a + b;
}

void g(void)
{
   int i, j = 12 , k = 23;

   sum(i, j, k);        // Ok.
   sum(k, i + j, 34);   // Ok.
   sum(5, i, j);        // Illegal.
   sum(i + j, i, k)     // Illegal.
   i = 1;
   j = 2;
   k = 3;
   sum(i, i + j, k);   // What is i's value after call?
}

Returning values through reference parameters vs. returning values under the function name.

Function Side Effects

Any modification by a function of a non-local (global variable, reference or pointer parameter) variable.

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?

Exercises

  1. Consider the Fibonacci sequence: 1, 1, 2, 3, 5, 8, 13, ...

    What's the relationship between members of the sequence? Write a recursive function which takes a parameter n and returns the value of the n'th member of the sequence. E.g., fib(6) returns 3.

  2. What is recursive about the choose function? (Its not obvious.) Write a non-trivially recursive version of the choose function.


Thomas P. Kelliher
Sun Apr 28 11:14:24 EDT 1996
Tom Kelliher