The factorial of a positive integer is the product of all nonnegative integers less than or equal to that number. (The symbol for factorial is "!" - the exclamation mark.)

The formula for factorials for all nonnegative integers is:

    n! = n(n-1)! for n > 0;

From this definition, 5! is 120.

   5! = 5 . 4 . 3 . 2 . 1 = 120

Zero factorial is a special case and 0! = 1

Write two methods to compute factorials. One method should use recursion, and the other method should use iteration.

Two rectangular mirrors of identical size are directly opposite each other on the opposite walls of a room. Due to the separation between the mirrors, the image of each mirror shrinks to two-thirds its size in the opposing mirror. This produces a series of rectangles of ever decreasing size in each mirror. Write a recursive program that produces this series of rectangles until a rectangle becomes so small as to become inconsequential.

Hint:
To read in a GIF or JPEG file, you need a Toolkit object. Use the static getDefaultToolkit method of the Toolkit class.

      String filename = "myimage.jpg";
      Image image = Toolkit.getDefaultToolkit().getImage(filename);

You can display an image with the drawImage method of the Graphics class.

Write a recursive program to compute the sum of the numbers from 1 to n, where n is a positive number greater than or equal to 1.

Although this problem is easy to solve iteratively, you must come up with a recursive solution.

A formula for finding the greatest common divisor (GCD) of two numbers was formulated by the mathematician Euclid around 300 BCE. The GCD of two numbers is the largest number that will divide into both numbers without any remainder. For example, the GCD of 12 and 16 is 4, the GCD of 18 and 12 is 6.

The basic algorithm is as follows:

If you divide one number by another, you will have a quotient and a remainder. If the remainder is 0, the divisor is the GCD.

If the remainder is greater than 0, divide the remainder into the divisor. If the new remainder is 0, the new divisor (the old remainder) is the GCD. If the new remainder is greater than zero repeat this step (divide the new remainder into the new divisor).

Write a recursive method that finds the GCD of two numbers using Euclid's algorithm.

Many fractals can be programmed using recursive methods. Those fractals using initiator/generator methods lend themselves to some elegant solutions using recursion. A modified version of the von Koch snowflake curve is described below.
The fractal begins with an initiator, or the shape we will fractalize. In this case it is a straight line:

     ______

Given the starting and ending points of a line, the program draws a "generator" in place of the line. In this example the generator consists of five connected line segments of equal length and looks like:

        __
     __| |__

The program then takes each new line segment in the figure and redraws a scaled down version of the generator in place of those lines.

The first three iterations of the program produce:

   ____________________

          ______
         |      |
         |      |
         |      |
   ______|      |______

            _
           __| |__
         _|       |_
      _ |_         _| _
    _| |__|       |__| |__


but without any breaks or gaps in the evolving fractal curve (a result of displaying the image above using text symbols). Write a program that generates this fractal graphically. Make sure you use a helper method to do the actual drawing of the generator.

Popular state lotteries consist of many sequentially numbered small balls. A subset of the small balls is chosen. If someone correctly predicts the numbers on the balls that were chosen, that person wins the lottery. The odds of winning a lottery can be computed by a combination. The formula for a combination is expressed as

C(n,r) = n! / (r! * (n-r)!)

n represents the number of balls in the lottery.
r represents the number of balls chosen.

Using recursion, write an applet that allows a user to enter the number of balls used in the lottery, and the number of balls chosen. Print out the odds of winning that lottery.

Write a program to draw the logarithmic spiral recursively.

The logarithmic spiral or Fibonacci spiral is a shape often found in nature. The nautilus shell is the classic example of the logarithmic spiral. Seed patterns in sunflowers and pinecones also demonstrate the spiral.



To construct a logarithmic spiral, begin with a golden rectangle. A golden rectangle is a rectangle with sides of length A and ΦA, where Φ (Phi) is the golden mean or the value ( 1 + sqrt(5) ) / 2 or 1.61803 . . . A square with length equal to the smallest side of the rectangle is drawn inside the rectangle. A quarter arc (arcAngle = 90 degrees) is drawn within this square. The remaining rectangle is also a golden rectangle. This remaining rectangle is divided into a square and another smaller golden rectangle. A quarter arc connected to the previous arc is drawn inside the square, and the remaining rectangle is once again subdivided with an arc drawn in it.

Hints:

In Java the height and width of the Rectangle class are stored as ints. Unless you keep track of a golden rectangle's dimensions as floating-point numbers, you will quickly lose precision and the resulting rectangles will not be drawn correctly.

Create a panel in which to draw the spiral:

   public class LogSpiralPanel extends Jpanel {

Given the dimensions of the panel, draw the largest golden rectangle that will fit within the panel. You will want to create a separate class to store the dimensions of the current golden rectangle and the current rotation.

Most calculators except input in the form of infix notation, that is

3 + 4

However, some calculators, including most Hewlett-Packard scientific calculators, use postfix notation or what is often referred to as Reverse Polish Notation or RPN. In this method, the operator comes after the operands. The postfix notation for 3+4 is

3 4 +

Another example,

Infix: ( 4 + 5 ) / 5 * 3 is <BR>
Postfix: 4 5 + 5 / 3 *

Write a program to convert infix notation to postfix notation.

A common programming error is an infinite recursion. Define infinite recursion and give an example of code that may cause infinite recursion.

Recursive programs usually take more time and use more memory than iterative programs. If this is the case, why would you ever write a program using recursion?

The golden mean, often referred to as the golden ratio, divine proportion, or the golden number is represented by the Greek letter phi ( Φ ). The value of the golden mean is (1 + sqrt(5)) / 2 or 1.61803 . . . The golden mean is found in nature and art and tends to yield the most "aesthetically pleasing" arrangements of objects.

Fibonacci numbers are directly related to the golden mean. The definition of Fibonacci numbers is

     fib(1) = 1
     fib(2) = 1
     fib(n) = (fib(n-1) + fib(n-2))

After the first two numbers, each of which has the value of 1, the next number in the Fibonacci sequence is the sum of the two preceding numbers.

Computing ratios of Fibonacci numbers can approximate the value of the golden mean. The value of.

    fib(n) / fib(n-1)

approximates the golden mean as n goes to infinity.

Write a recursive program to calculate the value of the golden mean to 12 significant digits. Make your program efficient; that is, do not recalculate values for Fibonacci numbers.