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.

References