Iteration and Recursion

Object-oriented programming with Java
Ahmed Al-Ajeli
Iteration and Recursion
Ahmed Al-Ajeli
Lecture 6
2
Topics to be covered
•Definite iteration
•Indefinite iteration
•Recursive methods
•Tracing recursive methods
Object-oriented programming with Java
Ahmed Al-Ajeli
3
Iteration
•Iteration is the process of doing something several times.
•To deal with iteration, most programming languages provide loop
statements
•A loop can be used to execute a block of statements repeatedly without having to write them multiple times.
4
Definite iteration
•It is used for tasks where you know for sure how many times some actions are performed.
•The for loop is well suited to situations requiring definite iteration.
Object-oriented programming with Java
Ahmed Al-Ajeli
5
The for loop
•The for loop is used to execute a set of statements a fixed number of times.
•The general form:
for(initialization; boolean condition;
post-body action){
loop body
}
•Loop body is executed while the boolean condition is true.
6
The for loop - examples
Ex1: down-up for
for(int i=1; i<11; i++){
System.out.println("Count
is: " + i);
}
Ex2: up-down for
for(int i=10; i>=1; i--){
System.out.println("Count
is: " + i);
}
Object-oriented programming with Java
Ahmed Al-Ajeli
7
Indefinite iteration
•It is used for tasks where you might want to stop partway through.
•The while and do-while loops are used for indefinite iteration.
8
The while loop
•The general form:
while (boolean condition){
loop body
}
•Example:
int count = 1;
while (count < 11){
System.out.println("Count is: " +
count);
count++;
}
While boolean condition is true, loop body is executed
Object-oriented programming with Java
Ahmed Al-Ajeli
9
The do-while loop
•The general form:
do{
loop body
}while(boolean condition);
•Example:
int count = 1;
do{
System.out.println("Count is: " +
count);
count++;
} while (count < 11);
While boolean condition is true, loop body is executed
10
Infinite loops
for ( ; ; ){
loop body
}
while (true){
loop body
}
int i=1;
while (i<10){
System.out.println (i= “ + i);
}
Object-oriented programming with Java
Ahmed Al-Ajeli
11
Recursion
•Recursion is a basic programming technique you can use in Java, in which a method calls itself to solve some problem.
•A method that uses this technique is recursive.
12
General form of recursion
if the stopping case is reached then
solve it
else
reduce the problem using recursion
…
…
Size n problem
Size n-1 problem
Size 2 problem
Size 1 problem
Size 1 problem
Size 1 problem
Size 1 problem
Object-oriented programming with Java
Ahmed Al-Ajeli
13
Recursion- Classic problem
•calculating the factorial of an integer n:
- 0! = 1
- n! = n * (n-1)!, for n>0
•Example: 5!=5 * 4 * 3 * 2 * 1 =120
public long factorial(int n)
{
if(n == 0){
return 1; // stopping case
}
else{ // recursive step
return n * factorial(n-1);
}
}
14
Tracing a recursive method
factorial(2)
n is 2
Is 2 = 0? false
return 2 * factorial (1)
n is 1 Is 1 = 0? false return 1 * factorial (0)
n is 0 Is 0 = 0? true return 1
Stack frame
1
2
1
Object-oriented programming with Java
Ahmed Al-Ajeli
15
n!- iterative solution
public long factorial(int n)
{ int f=1;
for(int i=2 ; i<=n ; i++){
f=f*i;
}
return f;
}
16
Programming exercise
•Write a recursive method, findSum, that calculates the sum of successive integers starting at 1 and ending at n (for example, findSum (n) = 1 + 2 + … + (n-1) + n)