Transcript Recursion

Thought for the Day
“The greatest crimes do not arise from a want of
feeling for others but from an over-sensibility for
ourselves and an over-indulgence to our own
desires.”
– Edmund Burke
Pre- and Postconditions and
Assertions
• Techniques for clarifying what a program is
doing
– “snapshots” or “checkpoints”
• Preconditions and postconditions
– Beginning and end of methods
• Assertions
– More generally
– May be checked at runtime
Automated Documentation
• Several current programming languages
provide automatic system documentation
facilities
• Java: Javadoc
– Special comments turned into HTML
documentation
System Development
javac
MyClass.class
MyClass.java
javadoc
MyClass.html
Example
/** The approximate square root is found using
*
the Newton-Raphson method.
* @param x The value whose square root is to
*
be calculated.
* @return The approximate square root of x.
*/
public static double squareRoot (double x)
{ . . .
} // squareRoot
End of Chapter 1
• Advanced programming
– Advanced data structures
– Advanced algorithms
– Program quality (efficiency)
• General program quality issues
• Preconditions, postconditions and assertions
• Automatic documentation
Chapter 2: Advanced
Programming Techniques
• Objectives
– Revise the use of recursion in programs
– Introduce interfaces in Java
Recursion
• Many problems are naturally recursive
– i.e. the solution is best expressed in terms of the
solution!
• A simple arithmetic example:
– factorials
n! = n × (n-1) × (n-2) × … × 3 × 2 × 1
Factorials
• How is this recursive?
n! = n × (n-1) × (n-2) × … × 3 × 2 × 1
= (n-1)!
• So: n! = n × (n-1)!
– The factorial function is defined in terms
of itself (i.e. recursively)
Recursive Calculation
of Factorials
n! = n × (n-1)!
• In order for this to work, we need a stop
case (the simplest case)
• Here: 0! = 1
A Recursive Factorial Function
in Java
int factorial (int n)
{ if (n == 0) // The stop case
return 1;
else
return n * factorial(n-1);
} // factorial
A recursive method call
How does this work?
int x = factorial(3);
6
factorial(3)
2
factorial(2)
1
factorial(1)
1
factorial(0)
int factorial (int n)
{ if (n == 0) // The stop case
return 1;
else
return n * factorial(n-1);
} // factorial
Recursion
• In general:
– We describe the solution to a problem in terms
of solving a slightly simpler version of the
same problem
– We must have a stop case: the simplest case
that can be solved on its own
Recursion
• While recursion can be used to solve many
problems it is not always the most efficient
solution
int factorial (int n)
{ int fact = 1;
for (int k = 1; k <= n; k++)
fact = fact * k;
return fact;
} // factorial