predicting process shape from procedure shape

what kind of process does our code generate?

• a recursive process
• because work is deferred: a chain of multiplications builds up

shapes of procedures

• how can we see in the code what work might be deferred?
• consider evaluation rules:
  special forms
  
  • define at start of body always happens first
  • if always executes condition first
  application
  • parts evaluated first
  • so, procedure is tail recursive if there is no recursive call
    in the conditional of an if special form
    
    within an application expression
  • roughly
    (define (f …) (f (g … ) … )) is tail-recursive and generates an iterative process
    
    (define (f …) (g (f … ) … )) is not tail-recursive and generates a recursive process

Previous slide

Next slide

Back to first slide

View graphic version