COMPSCI 1JC3 Lecture Notes - Lecture 5: Regular Expression, Linear Search, Kleene Algebra
Document Summary
Programming language is responsible for how its performed. Loops can be simulated space-efficiently by functions by tail recursion. Tail recursive if all computation is performed before a recursive call. We do all our computation then make recursion the last thing. Programmer is responsible for how the code is run. Programmer have to describe the function implicitly they have to also describe how to evaluate. Loops are more space-efficient than recursion because they take constant space. Loops are more space-efficient than recursion that don"t implement tail recursion properly. Natural number assignment for bigsum bigsum m n f. = 0 (this is because this is the identity element for addition) What natural number value should be assigned to the tuple (m,n,f) of inputs for bigsum: m, n, m - n. If m <= n then (n - m) + 1 else 0.