# Building Recurrence relations in plain readable English

`1,1,2,3,5,8,13,21,34,55…`
`fib(i) = fib(i-1) + fib(i-2)`
`function printReverse(n) {    if(n > 0) {        console.log(n)        printReverse(n-1)    }}`
`10987654321`
`function printReverse(n){ // If this requires T(n) time    if(n > 0) {           // This line executes in constant time = 1        console.log(n)    // This line executes in constant time = 1        printReverse(n-1) // This line executes in T(n-1) time    }}`
`When n <= 0    T(n) = 1 When n > 0    T(n) = 1 + 1 + T(n-1)   .: T(n) = 2 + T(n-1)   .: T(n) = T(n-1) + 2         ... 1`
`T(n) = 1            (for n <= 0) // This is our "base case"T(n) = T(n-1) + 1   (for n > 0)`
`function fibonacci(n) {  // If this requires T(n) time      if(n == 0 || n == 1) // This is a constant time operation = 1        return 1  // This is a constant time operation = 1    let i = fibonacci(n-1) // This requires T(n-1) time          let j = fibonacci(n-2) // This requires T(n-2) time    return i+j // This is also a constant time operation = 1}`
`When n >= 0 && n <= 1:    T(n) = 1 + 1    Which can be asymptotically written as    T(n) = 1When n > 1:    T(n) = 1 + T(n-1) + T(n-2) + 1    .: T(n) = T(n-1) + T(n-2) + 2    Which can be asymptotically written as:    T(n) = T(n-1) + T(n-2) + 1`

--

--