Transcript Introduction to Java - Tonga Institute of Higher Education

Iteration and
Recursion
Tonga Institute of Higher Education
Iteration
Iteration - Repeating a set of steps.
 Most programs contain loops where the
body of the loop is executed over and over
again.
 The computer iterates (repeats) through
the loop, which means that it repeatedly
executes the loop.

Simple Example of Iteration
Name: Sione Name: Mele Name: Semisi Name: Poli Name: Ana
Salary: 400
Salary: 410 Salary: 430
Salary: 900 Salary: 300
First add
40 here




Then add
40 here
Then add
40 here
Then add
40 here
Finally, add
40 here
We have an array that stores employee objects
for the employees in your company.
We want to give each employee a 40 pa’anga
raise.
We could try to find each employee in the array
and give them a raise but that takes a long time.
It is better to iterate through each employee and
give each one a raise.
Triangular Numbers




Pythagoras was a famous mathematician in
ancient Greece. He made the Pythagorean
theorem.
He had some people who worked under him
who called themselves the Pythagorians.
The believed that this series of numbers was
magical:
1, 3, 6, 10, 15, 21, 28 …
Can you see the pattern in these numbers?
The Pattern of Triangular Numbers
Number
Calculation
1
2
3
4
5
6
7
By Definition
1+2
1+2+3
1+2+3+4
1+2+3+4+5
1+2+3+4+5+6
1+2+3+4+5+6+7
Triangle
Number
1
3
6
10
15
21
28
Why are they “Triangular”
Numbers?

They can be seen as a triangular arrangement
of objects, shown as little squares below.
Triangular Number Calculation with
Iteration – 1
Subtract one every
time we add to the
total

To find 4th Triangular
Number can add the
number of squares in
each column.
Triangular Number Calculation with
Iteration – 2
Change this to be the Triangular
Number you want to find
Subtract one every
time we add to the
total
Used to calculate
and store the
Triangular
Number
Demonstration
Triangular Numbers
Iteration
Project: TriangularNumber
Recursion



Recursion - A programming method in which a method
calls itself.
Recursion is an extremely powerful concept, but it can
strain a computer's memory resources.
Recursive algorithms follow a divide-and-conquer
approach.
1.
2.
3.
Divide the problem into a number of subproblems.
Conquer the subproblems. If the subproblem is too hard, divide
it again until it is small enough to solve easily.
Combine the solutions to the subproblems into a solution for the
original problem.
Triangular Number Calculation with
Recursion – 1

To find 4th Triangular
Number can add:
1.
2.
The tallest column,
which has a value of 4.
The sum of all the
remaining columns,
which is 6.
Triangular Number Calculation with
Recursion – 2

To find 4th Triangular Number can add:
1.
2.
The tallest column.
The sum of all the remaining columns.
1
Adds the tallest column to
The sum of the columns
2
Adds the tallest column to
The sum of the remaining columns
3
The sumAllColumns method does
the same thing as triangle. So
replace sumAllColumns with triangle
Triangular Number Calculation with
Recursion – 3

This approach works like this:













Someone tells me to find the 4th Triangular number.
I know: (4th Triangular number) = (3rd Triangular number) + 4.
So I tell Sione to find the 3rd Triangular number.
Sione knows: (3rd Triangular number) = (2nd Triangular number) + 3
So Sione tells Ana to find the 2nd Triangular number.
Ana knows: (2nd Triangular number) = (1st Triangular number) + 2
So Ana tells Taniela to get the 1st Triangular number.
Taniela knows that the 1st Triangular number so he tells Ana 1
Ana tells Sione the 2nd Triangular number is 1 + 2 = 3
Sione tells me that the 3rd Triangular number is 3 + 3 = 6
So I know that the 4th Triangular number is 6 + 4 = 10
At some point, we stop asking others and provide an answer.
If we never provide an answer, we will be asking questions forever.
Triangular Number Calculation with
Recursion – 4

At some point, we stop asking others and
provide an answer.
3
Previously coded step
4
We stop asking here and
give an answer
Triangular Number Calculation with
Recursion – 5
Change this to be the Triangular
Number you want to find
Begins the
recursive
process
We stop asking here and
give an answer
We call this method over
and over again
Demonstration
Triangular Numbers
Recursion
Project: TriangularNumber
Demonstration
Triangular Numbers
Recursion w/ Outputs
Project: TriangularNumber
Characteristics of Recursive
Methods
It calls itself
 When it calls itself, it does so to solve a
smaller problem
 At some point, the problem is simple
enough so the method can return
something without calling itself.

Is Recursion Efficient?

Recursion is not as efficient as iteration
 Methods
must be called over and over again
 All the variables in all the methods must be
stored while methods calls are repeated
Why Use Recursion?

Recursion simplifies problems conceptually.
Factorial Calculation with
Recursion - 1
Number
1
2
3
4
5
6
7
Calculation
By Definition
1*2
1*2*3
1*2*3*4
1*2*3*4*5
1*2*3*4*5*6
1*2*3*4*5*6*7
Factorial
1
2
6
24
120
720
5040
Class Competition
Develop the program to find a
factorial using the triangular
number program.
Demonstration
Factorials
Project: Factorial
Factorial Calculation with
Recursion - 2
Change all words that say
triangular to factorial
Multiply instead of Add