# 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.

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