recursive.java

国外的数据结构与算法分析用书

import dslib.list.BasicListUos;
import dslib.exception.*;

public class Recursive
{
	/**	The value of the nth Fibonacci number.
		PRECONDITION:
			n >= 0 */
	public int fibonacci(int n)
	{
		if (n < 0)
			throw new InvalidArgumentUosException("n cannot be negative");
		if (n == 0 || n == 1)
			return 1;
		return fibonacci(n - 1) + fibonacci(n - 2);
	}

	/**	The value of n!.
		Analysis: Time = O(n)
		PRECONDITION:
			n >= 0 */
	public int factorial(int n)
	{
		if (n < 0)
			throw new InvalidArgumentUosException("n cannot be negative");
		if (n == 0)
			return 1;
		return n * factorial(n - 1);
	}

	/**	The largest value in the part of array arr from index low to high, inclusive.
		Analysis : Time = O(high - low + 1)
		PRECONDITION:
			high >= low
			!(low < 0 || high >= arr.length) */
	public int largestValue(int[] arr, int low, int high) throws InvalidArgumentUosException
	{
		if (low > high)
			throw new InvalidArgumentUosException("invalid search range");
		if (low < 0 || high >= arr.length)
			throw new InvalidArgumentUosException("searching outside of the array");

		if (low == high) // base case: only one value
			return arr[low];
		/*	Recursive case: the result is the larger of the first value 
			(in position low) and the largest of the remaining values. */
		return Math.max(arr[low], largestValue(arr, low + 1, high));
	}

	/**	String representation of the value of n.
		Analysis : Time = O(number of digits in n)
		PRECONDITION:
			n >= 0 */
	public String toString(int n) throws InvalidArgumentUosException
	{
		if (n < 0)
			throw new InvalidArgumentUosException("n cannot be negative");

		String result;
		if (n < 10)
			result = "0123456789".substring(n, n + 1);
		else
			result = toString(n / 10) + toString(n % 10);
//		assert result.equals(Integer.toString(n));
		return result;
	}

	/**	The length of theList.
		Analysis : Time = O(k*c), k = length of list, c = time for first-remainder */
	public int listLength(BasicListUos theList)
	{
		if (theList.isEmpty())
			return 0;
                 else
			return 1 + listLength(theList.firstRemainder());
	}

	/**	Insert theValue at the right end of theList.
		Analysis : Time = O(k*c), k = length of thelist and 
					  c = time for firstRemainder + time for setFirstRemainder
		PRECONDITION:
			!theList.isFull() */
	public void insertLast(BasicListUos theList, Object theValue) throws ContainerFullUosException
	{
		if (theList.isFull())
			throw new ContainerFullUosException("Cannot insert at the end of a full list");
	
		if (theList.isEmpty())
			theList.insertFirst(theValue);
		else
		{
			BasicListUos rem = theList.firstRemainder();
			insertLast(rem, theValue);
			theList.setFirstRemainder(rem);
		}
	}

	/**	Insert theValue at the right end of theList.
		Analysis : Time = O(k), k = length of thelist
		PRECONDITION:
			!theList.isFull() */
	public void insertLastV2(BasicListUos theList, Object theValue) throws ContainerFullUosException
	{
		if (theList.isFull())
			throw new ContainerFullUosException("Cannot insert at the end of a full list");

		if (theList.isEmpty())
			theList.insertFirst(theValue);
		else
		{
			Object firstItem = theList.firstItem();
			theList.deleteFirst();
			insertLastV2(theList, theValue);
			theList.insertFirst(firstItem);
		}
	}
}