C S 314 Chapter Notes - Chapter 3: Linked List, Doubly Linked List, Infinite Loop

• School: UT-Austin
• Department: Computer Science
• Course: C S 314
• Professor: Novak Gordon

Document Summary

Some guidelines for designing recursive functions: write a clear definition of what your function should do, including inputs, outputs, assumptions. There are two common ways of making the input smaller: remove a piece of the input, e. g. remove the first element from a linked list, cut the input in half, e. g. follow one branch of a tree. A design pattern is an abstracted way of writing programs of a certain kind. By learning design patterns, you can write programs faster and with fewer errors. A design pattern for recursive functions is: (defun myfun (arg) (if (basecase? arg) (baseanswer arg) (combine arg (myfun (smaller arg))))) Exercise: show how the factorial function corresponds to this design pattern. A function is tail recursive if it either returns an answer directly, e. g return 0; the answer is exactly the result of a recursive call, return myself( something); Tail recursion often involves the use of an extra function with extra variables as parameters.