COSC 350: Data Structures
March 18, 2009

Recursion: Examples and Practice

Definition of Recursion: A function that calls itself

Rules of (Terminating) Recursion:
1. Must have a terminating base case
2. Must test for base case before recursive call
3. Recursive call must move toward base case

Costs of Recursion

Recursion and Complexity

Linear Recursion vs Tree Recursion

Homework

1. Write a recursive program to multiply the number of items in a list. E.g., multiply([1,2,3,4]) -> 24
2. Write a recursive program that discards everyother item from a list. E.g., weed([1,2,3,4,5]) -> [1,3,5]

This page was created by Joe Sloan.
It was last modified on or after: 20 March 2009
Send mail to: sloanjd@wofford.edu