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:

• Apr. 29: 9.1, 9.2, 9.4--9.8.
• May 1: Additional scalar types; arrays. 10.1, 10.2, 12.1--12.3. Homework 6 in, homework 7 out.
• May 3: Homework discussion (Using data files. 14.1--14.3).
• May 6: Using 1-D arrays. 12.4--12.6
• May 8: 2-D arrays, Homework lab. 12.7.
• May 10: Character data and Strings. 13.1--13.3.
• May 13: String processing. 13.4--13.6. Homework 7 in.
• May 14: A final review will be put on the homepage. I will be out of town from the evening of the 13th through the evening of the 15th.

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:

• Use & in a declaration to create a reference variable.
• The initialization is required.
• The reference variable shares memory with the initializer variable.
• The types of the two variables must match exactly.
• In an expression, & is the address of operator. It can be applied only to variables.

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:

• The normal rules for value parameters apply: Type matching, etc.
• The formal parameter is declared as a reference variable.
• The actual parameter must be a variable and nothing else.

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.

• You may not be aware of side effects.
• It's easy to forget about side effects.
• They have their place, but must be used with discipline.

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.