I&C SCI 46 Lecture Notes - Lecture 6: Iterated Function, Gödel, Escher, Bach, Linked List

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

Document Summary

In this lecture we will discuss the concept of recursion and examine recursive functions that operate on integers, strings, and linked lists, learning common idioms for each. When we cover linked lists, will first examine functions operating on linked lists that do not change their structure, and then examine functions whose purpose is to change the structure of the linked list (add or remove values). We will study how to hand simulate such functions and the three rules for proving them correct. In addition, some programming languages (lisp is the foremost example) use recursion (and also decision-if) as their primary control structures: any iterative code can be written recursively. Even languages that are not primarily recursive all support recursion (and have since the late 1950s), because sometimes using recursion is the best way to write code to solve a problem. C++ (and java/python) are not primarily recursive languages.