// == (Sequence) Abstractions ==
// (i.e., map, filter, any, all, ...)

// Generally great to use when...
// - strong match to the task
//   (helping you, communicating to others)
// - you are ok with some loss of resource efficiency
//   (benefit to provenance!)

// SO...
// - avoid re-implementation
// - use best-match (last=fold)


























// == Recursion (vs Iteration/Looping) ==

// General approach
// - (more when non-linear!)
// - Beneficial for simplicity, analysis

// Most languages = overhead
// - each function call requires extra time+memory
// - risk of stack overflow

// Note: ALL RECURSION CAN BE CONVERTED TO ITERATIVE

// SO, avoid unless...
// - recursion leads to substantial simplification; AND
// - "size" of the problem ~ small (no stack overflow)
















// compute nth element in Fibonnaci sequence (for non-negative n)
// https://en.wikipedia.org/wiki/Fibonacci_sequence

// recursive: fib(0)=0, fib(1)=1, fib(n) = fib(n-1) + fib(n-2)
fun fibRecursive(n: Int): Int {
    return when (n) {
        0 -> 0
        1 -> 1
        else -> fibRecursive(n-1) + fibRecursive(n-2)
    }
}

println(fibRecursive(10))
println(fibRecursive(19))
// println(fibRecursive(48))






















// iterative: keep track of prior two values
fun fibIterative(n: Int): Int {
    return when (n) {
        0 -> 0
        1 -> 1
        else -> {
            var nMinus2 = 0
            var nMinus1 = 1
            var result = 0
            
            for (i in 2..n) {
                result = nMinus2 + nMinus1
                nMinus2 = nMinus1
                nMinus1 = result
            }
            
            result
        }
    }
}

println(fibIterative(10))
println(fibIterative(19))
println(fibIterative(48))