============================================================================
           Faculty of Applied Science and Engineering, University of Toronto
                     CSC181: Introduction to Computer Programming, Fall 2000

Tutorial Notes, Week 8
============================================================================

-----------------
Summary of Topics
-----------------

- Recursion

------------------
Example: Fibonacci
------------------

The Fibonacci numbers are a sequence of numbers, F_0, F_1, F_2,
... defined recursively as follows:

F_0 = 0,
F_1 = 1,
F_n = F_{n-1} + F_{n-2}  for n >= 2.

Below is the code for computing the nth number in the Fibonacci
sequence.

/* Compute and return F_n (the nth Fibonacci number).
   Precondition: n >= 0. */
int fib(int n) {
	if (n == 0 || n == 1)
		return n;
	else
		return fib(n-1) + fib(n-2);
}

----------------------------------
Example: Working with Linked Lists
----------------------------------

We want to write a function that, given l, a list of integers (which
is implemented using a singly-linked list, in this case) and an
integer n, returns the smallest integer in l larger than n in the
list.

(What would be a sensible value to return if there is no integer in l
greater than n?)

int recListSmallestLarger(const ListNodePtr x, int n) {
	if (x == NULL)
		return n-1;
	else {
		int rest = recListSmallestLarger(x->next, n);
		if (x->data > n && rest > n)
			return min(x->data, rest);
		else if (x->data > n)
			return x->data;
		else
			return rest;
	}
}

/* Returns the smallest integer in the given list that is larger than n,
   or n-1 if there is no integer greater than n in the list. */
int listSmallestLarger(const ListPtr l, int n) {
	return recListSmallestLarger(l->front, n);
}