COSC 350: Data Structures
March 20, 2009

Wrap Up Recursion:

Uses: Divide and Conquer, Greedy Algorithms, Search

Costs of Recursion

Recursion and Complexity

Linear Recursion vs Tree Recursion

Implementing Recursion

Subroutine calls and activation records

Python aborts if it has too many pending recursion calls. This is the recursion limit.
You can change this limit with the SYS module using the commands:

sys.getrecursionlimit()
sys.setrecursionlimit(limit)

Tree Vocabulary

Root, Leaf, Vertex or Node, Edge, Parent, Child, Sibling, Ancestors, Descendants
Height, Path, Path Length
Binary Tree, N-ary Tree, Subtree, Left Subtree, Right Subtree, Left Child, Right Child,
Tree Traversal

Homework

Rewrite programs 5.2, 5.3, and 5.6 in Python.

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