Recursion - Absolute Java - page 683

14. public static double power( int x, int n)
{
if (n < 0 && x == 0)
{
System.out.println(
"Illegal argument to power.");
System.exit(0);
}
if (n < 0)
return ( 1/power(x, - n));
else if (n > 0)
return ( power(x, n - 1)*x );
else // n == 0
return (1.0);
}
15. public static int squares( int n)
{
if (n <= 1)
return 1;
else
return ( squares(n - 1) + n*n );
}
16. One approach is to keep a list of all directories that have been encountered. The
list could be implemented with an array. Initially, this list would be set to the root
directory. While there is at least one directory on the list, repeat the following:
• Remove a directory from the list.
❍ Find all files within the directory. If one of these files matches the target,
return the pathname to the file.
❍ Find all subdirectories within the directory. Add each subdirectory to
the list.
This approach is a little more complicated than the recursive version because we
have to manage the list. In the recursive version, the list is essentially managed for
us through the series of recursive calls.
17. A stack overflow in the context of recursion occurs when there is a long chain of
recursive calls. In the FindFile program, one link of this chain is created when a
subdirectory is in another directory. To create a stack overflow, we would need to
have a folder in a folder, which is in a folder, which is in a folder, etc. How many
folders must be linked in this way to cause a stack overflow will vary from one
system to another, but you can expect hundreds would be necessary, an unlikely
scenario in a typical file system. Although there could be thousands of recursive
calls when searching for a file, there will likely be many short chains instead of
single long chains. This allows recursive calls to exit and prevent a stack overflow.
18. Recursion stops if the file passed in is not a directory, if there are no subdirectories
in the directory, or after all subdirectories have been recursively called. If a match
is found, then recursion also stops.