Chapter 3 · Data
Math and recursion
Step 1 of 19 · Concept
Math does the arithmetic
In this lesson you use Java's ready-made math, then write methods that call themselves.
The class Math holds static methods, called on the class's name (lesson 6). It needs no import.
| call | gives |
|---|---|
Math.max(3, 8) | 8, the larger |
Math.min(3, 8) | 3, the smaller |
Math.abs(-5) | 5, the value without its sign |
Math.pow(2, 10) | 1024.0: 2 to the power 10 |
Math.sqrt(49) | 7.0, the square root |
Step 2 of 19 · Concept
From double to int: a cast
Math.pow and Math.sqrt always return a double. That is why Math.pow(2, 10) prints as 1024.0.
To make an int of a double, write (int) in front of it. This is a cast: it cuts off the fraction. It
does not round.
double root = Math.sqrt(50); // 7.0710678118654755
int whole = (int) root; // 7
Step 3 of 19 · Quiz
Cut, not rounded
What is (int) 9.99?
Step 4 of 19 · Concept
Random numbers you can repeat
Random makes random numbers. It lives in java.util, like Scanner, so it needs import java.util.Random;.
Random dice = new Random(42);
int roll = dice.nextInt(6) + 1; // 1 to 6
dice.nextInt(6)gives a whole number from 0 to 5, so+ 1makes it a die.42is the seed, a starting number. The same seed gives the same numbers on every run: a test can check them.new Random()without a seed starts somewhere new each time.
Step 5 of 19 · Demo
Math and Random at work
Run it. Look at the types: 1024.0 and 7.0 are doubles, 7 is a cast. With the seed 42 the rolls are always
3, 4 and 1.
Step 6 of 19 · Exercise
Your turn: two kinds of distance
Write two methods for the distance from the point (x1, y1) to (x2, y2). Each takes four ints.
straightreturns adouble: the square root of (x2 - x1)² + (y2 - y1)².stepsreturns anint: the moves a piece needs if it only goes across or up and down. That is the size of x2 - x1 plus the size of y2 - y1.
The program must print:
Straight: 10.0
Steps: 14
Squared is Math.pow(…, 2), the square root is Math.sqrt, and "the size of" is Math.abs.
The headers are static double straight(int x1, int y1, int x2, int y2) and static int steps(…) with the same
four parameters.
static int steps(int x1, int y1, int x2, int y2) {
return Math.abs(x2 - x1) + Math.abs(y2 - y1);
}
Step 7 of 19 · Concept
A method that calls itself
A method may call itself: that is recursion. It solves a problem by solving a smaller one of the same kind.
static int factorial(int n) {
if (n == 0) {
return 1;
}
return n * factorial(n - 1);
}
factorial(3) is 3 * 2 * 1, which is 3 * factorial(2). The base case, n == 0, answers at once,
without calling itself.
Step 8 of 19 · Quiz
Where does it stop?
Which call of factorial returns without calling factorial again?
static int factorial(int n) {
if (n == 0) {
return 1;
}
return n * factorial(n - 1);
}
Step 9 of 19 · Trace
Frames pile up
Each call gets its own frame with its own n (lesson 6). Press Next and watch the stack grow and shrink.
static int factorial(int n) {
if (n == 0) {
return 1;
}
return n * factorial(n - 1);
}
public static void main(String[] args) {
System.out.println(factorial(3));
}maincalledfactorial(3): a frame withn= 3 sits onmain's. Line 2 asks ifnis 0.- 3 is not 0, so line 5 called
factorial(2). A new frame, with its ownn, sits on top. - 2 is not 0 either:
factorial(1)gets a frame. The calls under it wait for their answers. factorial(1)calledfactorial(0). Nownis 0: the base case. Line 3 returns 1 without a call.factorial(0)returned 1, and its frame is gone.factorial(1)works out1 * 1on line 5.factorial(1)returned 1, and its frame is gone.factorial(2)works out2 * 1.factorial(2)returned 2.factorial(3)works out3 * 2. The frames go newest first.factorial(3)returned 6 tomain, which printed it.mainended, and the stack is empty.
Step 10 of 19 · Concept
Two calls: Fibonacci
The Fibonacci numbers start 0, 1. Each next one is the sum of the two before it: 0, 1, 1, 2, 3, 5, 8, …
static int fib(int n) {
if (n < 2) {
return n;
}
return fib(n - 1) + fib(n - 2);
}
fibcalls itself twice: once for each number before.- It has two base cases,
fib(0)is 0 andfib(1)is 1.n < 2covers both with onereturn n.
Step 11 of 19 · Quiz
Count along
fib(5) is 5. What is fib(6)?
static int fib(int n) {
if (n < 2) {
return n;
}
return fib(n - 1) + fib(n - 2);
}
Step 12 of 19 · Demo
Factorial and Fibonacci
Run it. 5! is how math writes factorial(5). The loop in main calls fib for each n from 0 to 10.
Step 13 of 19 · Exercise
Your turn: the sum of the digits
Write sumDigits(int n) with recursion, for any n of 0 or more.
- The last digit of
nisn % 10, andn / 10isnwithout it (lesson 3). - So the sum of the digits of 2026 is 6 plus the sum of the digits of 202.
- A number under 10 is its own sum.
The program must print 7 6 10 45.
The base case: when n < 10, return n itself.
Otherwise: the last digit plus the sum of the digits of the rest, sumDigits(n / 10).
if (n < 10) {
return n;
}
return n % 10 + sumDigits(n / 10);
Step 14 of 19 · Concept
No base case: the stack fills up
Without a base case, the calls never stop: factorial(0) calls factorial(-1), and so on.
Each waiting call keeps its frame on the stack. The stack has a fixed size. When it is full, the JVM throws a
StackOverflowError, and the program ends.
Step 15 of 19 · Demo
A missing base case
Run it, and read the stack trace as in lesson 4. Every line says Forever.java:3: the same call over and over.
Java prints only the newest 1024 frames, so main does not even show.
Step 16 of 19 · Quiz
Where is the fix?
What does Forever need so that it stops?
public class Forever {
static int factorial(int n) {
return n * factorial(n - 1);
}
public static void main(String[] args) {
System.out.println(factorial(5));
}
}Step 17 of 19 · Check yourself
Check yourself: power, dice and stars
Write the three methods, each as its comment says, without changing main. The comments in main say what each
line prints.
power and stars have the shape of factorial: a base case, then one call on a smaller number.
Step 18 of 19 · Challenge · optional
Challenge: backwards
Optional. It earns the lesson's third star.
Write backwards with recursion: it returns its text backwards. Here the smaller problem is a shorter text. The
program must print:
desserts
avaJ
The base case is the empty text, text.length() == 0: backwards, it is still "".
Otherwise, take the text without its first character, text.substring(1), turn that backwards, and put the first
character after it.
return backwards(text.substring(1)) + text.charAt(0);
Step 19 of 19 · Recap
Recap
Mathhasmax,min,abs,powandsqrt. A cast(int)cuts off the fraction.new Random(42)gives the same numbers on every run;nextInt(6) + 1is a die.- A recursive method calls itself on a smaller problem. Its base case answers without a call.
- Each call has its own frame. Without a base case, the stack fills up:
StackOverflowError.
Next: lesson 13 keeps many values in lists and maps, which grow as the program adds to them.
Review
4 questions from this lesson, in a new order each time. Answer from memory: 3 of 4 right on the first try passes. On a day after you finish the lesson, a pass earns 15 XP.
The review needs JavaScript.
import java.util.Random;
public class Tools {
public static void main(String[] args) {
System.out.print(Math.max(3, 8) + " " + Math.min(3, 8));
System.out.println(" " + Math.abs(-5));
System.out.print(Math.pow(2, 10) + " ");
System.out.println(Math.sqrt(49));
System.out.println((int) Math.sqrt(50));
System.out.println(Math.max(2, 7.5));
Random dice = new Random(42);
for (int i = 1; i <= 3; i++) {
int roll = dice.nextInt(6) + 1;
System.out.println("Roll " + i + ": " + roll);
}
}
}
public class Distance {
// write straight here: it returns a double
// write steps here: it returns an int
public static void main(String[] args) {
double d = straight(2, 3, -4, -5);
System.out.println("Straight: " + d);
System.out.println("Steps: " + steps(2, 3, -4, -5));
}
}
public class Recursion {
static int factorial(int n) {
if (n == 0) {
return 1;
}
return n * factorial(n - 1);
}
static int fib(int n) {
if (n < 2) {
return n;
}
return fib(n - 1) + fib(n - 2);
}
public static void main(String[] args) {
System.out.println("5! = " + factorial(5));
String line = "Fibonacci:";
for (int n = 0; n <= 10; n++) {
line += " " + fib(n);
}
System.out.println(line);
}
}
public class Digits {
static int sumDigits(int n) {
// the base case first, then a smaller call
return 0;
}
public static void main(String[] args) {
System.out.print(sumDigits(7) + " ");
System.out.print(sumDigits(123) + " ");
System.out.print(sumDigits(2026) + " ");
System.out.println(sumDigits(99999));
}
}
public class Forever {
static int factorial(int n) {
return n * factorial(n - 1);
}
public static void main(String[] args) {
System.out.println(factorial(5));
}
}
import java.util.Random;
public class Check {
// base times itself, exp times, with recursion;
// power(base, 0) is 1
static int power(int base, int exp) {
return 0;
}
// one die: a number from 1 to 6
static int roll(Random dice) {
return 0;
}
// a text of n stars, with recursion;
// stars(0) is ""
static String stars(int n) {
return "";
}
public static void main(String[] args) {
// 1024 = 1024
System.out.print(power(2, 10) + " = ");
System.out.println((int) Math.pow(2, 10));
// 81 = 81
System.out.print(power(3, 4) + " = ");
System.out.println((int) Math.pow(3, 4));
Random dice = new Random(2026);
// ******, *****, **, *
for (int i = 0; i < 4; i++) {
System.out.println(stars(roll(dice)));
}
}
}
public class Backwards {
// text backwards, with recursion;
// backwards("") is ""
static String backwards(String text) {
return text;
}
public static void main(String[] args) {
System.out.println(backwards("stressed"));
System.out.println(backwards("Java"));
}
}