COMP 302 Lecture Notes - Lecture 3: Call Stack, Negative Number, Exponentiation
17 Feb 2017
School
Department
Course
Professor
Document Summary
Non tail-recursive program fact n = if n=0 then 1 else n * fact(n-1) We should be used to recursion by now; recursion means using the function you are defining in its definition. If you call fact 3 ", then it computes 3 * fact(2) . It then needs to solve 3*(2*fact(1)) , then 3*(2*(1*fact(0))) finally, it knows what factorial of 0 is (because we have our base case). So it can go up the chain and solve the rest. Tail recursive program fastfact(n,m) = if n=0 then m else fastfact(n-1, n*m) Requirements: there is only one recursive call (true in the program above as well), recursive call is outermost. Above, the outer operation include the recursive call, and each operation is suspended until all recursive computations are computed. In the tail recursion, nothing has to happen first". Any arithmetic happens inside the recursive call. fastfact(3,1) You don"t need a runtime stack to run it.
