Iteration & Recursion
Intent
Iterarion. An iterative function is one that loops to repeat some part of the code.
Recursion, is one that calls itself again to repeat the code.
Problem
Finding patterns that can recognise, but which are also worthwhile uses of recursion.
Example
sumNumber() using iterative approach:
public int sumNumberIterative(int numbers) {
int result = 0;
for (int i = 0; i < numbers; i++) {
result = result + i;
}
}
sumNumber() using recursive approach:
public int sumNumberRecursive(int numbers) {
// base case for termination
if (numbers == 1) {
return 1;
}
return numbers + sumNumberRecursive(numbers - 1);
}
Rules of Thumb
Iteration
- A set of instructions repeatedly executed.
- Termination when the condition for the iterator ceases to be satisfied.
- Used when time complexity needs to be balanced against an expanded code size.
- Time complexity, Relatively lower time complexity(generally polynomial-logarithmic).
Recursion
- Function calls itself.
- Termination through base case, where there will be no function call.
- Used when code size needs to be small, and time complexity is not an issue.
- Time complexity, very high(generally exponential) time complexity.