I&C SCI 33 Lecture 13: [Recursive Functions]

• School: UC-Irvine
• Department: Information and Computer Science
• Course: I&C SCI 33
• Professor: Richard Pattis

Document Summary

Recursion vs iteration: recursion is a programming technique in which a call to a function results in another call to that same function. In direct recursion, a call to a function appears in the function"s body. Iterative solution : visit 100,000 people, and ask each for a penny. Proof rules for recursive functions: the three proof rules should be simple to apply in most cases. These rules mirror rules for proofs by induction in mathematics. (1) prove that the base case (smallest) problem is processed correctly. Should be easy, because base cases are tiny and their solutions simple. (2) prove that each recursive call is on a smaller-sized problem: the problem gets closer to the base case. Should be easy, because we get to assume something very important and powerful: all sub-problems are solved correctly. Mathematics recursively: we can construct all the mathematical and relational operators on natural numbers (integers >= 0) given just three functions and if/recursion.