Recursion Induction Duality

Recursion is informally the Computational Dual of Induction.
Induction tells us some chain of increasing P(n) is true.
Recursion uses that knowledge of induction to safely climb down that chain of truths to the base case.
-me

Induction comes from your thoughts and algorithm design.
Recursion comes from the code being executed.

def identity(k):
    if k == 0:
        return 0
    if k == 1:
        return 1
    else:
        return 1+identity(k-1)

• In inductive proofs, \(P(k-1) \overset{proves}\Rightarrow P(k)\)
  • we assume id(k-1) is correct to design an algorithm for id(k).
    
• But computationally or recursively, id(k-1) \(\overset{reduce}\Leftarrow\) id(k)

Induction can be thought as a meta-level confirmation that computable recursion will work.

0.0.1 Diagrams

The lifelines of the Sequence diagram(the rectangular boxes) stacked on each other indicates a recursive function.
We can take advantage of this stacking behavior to implement recursion using stacks.

let x = "aababa"

const fun = (input) => {
    if(input.length != 0){
        let consumed = input[0]
        let rest = input.slice(1)
        if(consumed == 'b' && input.length == 1){
            return true 
        }else if(consumed == 'b' && input.length != 1){
            return false
        }else if(consumed == 'a'){
            return true && fun(rest)
        }
        else{
            return false
        }
    }else{
        return true
    }
}

console.log(fun(x));