Transcript Document

Recursion: Linear and Tree
Recursive Processes and Iteration
CMSC 11500
Introduction to Computer Programming
October 7, 2002
Roadmap
• Recap: Lists and Structural Recursion
• Structural Recursion (cont’d)
– Returning lists from procedures
– Hierarchical lists: lists of lists
– Tree-structured Recursion
• Generative recursion (Problem-based)
– Linear recursive processes
– Iteration
• Order of growth & exponentiation
Recap: Lists: Self-referential data
• Recap: Lists and Structural Recursion
– Arbitrarily long data structures
• Lists: Constructor: cons; Selectors: car, cdr
• Data definition: 1) empty list ‘() 2) (cons x alist)
– Self-referential definition
– Manipulating lists: Structural Recursion
• Self-referential procedures
• Need cases for:
– 1) Empty list
– 2) Compound case: Consume first (car) value; Call
function on rest of list (cdr)
Returning Lists: Square-list
Description: Take a list of numbers as input,
return a list of numbers with each of the values squared
(define (square-list numlist)
(cond ((null? numlist) ‘())
(else (cons (square (car numlist))
(square-list (cdr numlist))))))
Lists of Lists
• Can create lists whose elements are lists
– “closure” property of cons
• Objects formed by cons can be combined with cons
– Allows creation of hierarchical data structures
• (cons (list 1 2) (list 3 4)) => ((1 2) 3 4)
3
1
2
4
Tree Recursion
• Before: Assumed all lists “flat”
Now: Allow possibility of lists of lists
(define (square-tree alist)
(cond ((null? alist) ‘())
((not (pair? alist)) (square alist))
(else (cons (square-tree (car alist))
(square-tree (cdr alist))))))
Generative Recursion
• Syntactically recursive:
– Procedure calls itself
• Self-reference:
– Property of solution to problem
• Rather than data structure of input
– E.g. Factorial:
• n! = n*(n-1)*(n-2)*….*3*2*1
• n! = n*(n-1)!
– Function defined in terms of itself
Recursion Example: Factorial
(define (factorial n)
(if (= n 1)
1
(* n (factorial (- n 1)))
N=4
(* 4 (factorial 3))
(* 4 (* 3 (factorial 2)))
(* 4 (* 3 (* 2 (factorial 1))))
(* 4 (* 3 (* 2 1))))
(* 4 (* 3 (* 2 1)))
(* 4 (* 3 2))
(* 4 6)
24
Recursion Components
• Termination:
– How you stop this thing????
– Condition& non-recursive step: e.g. (if (= n 1) 1)
– Reduction in recursive step: e.g. (factorial (- n 1))
• Compound and reduction steps
– “Divide and conquer”
• Reduce problem to simpler pieces
• Solve pieces and combine solutions
Linear Recursive Processes
• How does the procedure use resources?
– Time: How many steps?
– Space: What do we have to remember
• Factorial:
– Time: n multiplications
– Space: Builds up deferred computations
• Interpreter must remember them
• Needs space for n remembered computations
Factorial: Iterative Process
(define factorial (fact-iter 1 1 n))
(define fact-iter (product counter max-count)
(if (> counter max-count)
product
(fact-iter (* counter product)
(+ counter 1)
max-count)))
(fact-iter 1 1 4)
(fact-iter 1 2 4)
(fact-iter 2 3 4)
(fact-iter 6 4 4)
(fact-iter 24 5 4)
24
Iterative Process
• Same computations as recursive factorial
– Time: n multiplications
– Space: constant: no deferred steps to remember
• Key:
– State of computation captured by variables
• product, counter: how much has been done so far
– If have state, could restart process