Interpreters
Interpreters
Tail Recursion
Tail Recursion
Tail Recursion An expression in a tail context is evaluated as the last step the function call o That means nothing is evaluated/applied after it is evaluated Function calls in a tail context are called tail calls If all recursive calls are in tail contexts,we say that function is tail recursive 0 If a language supports tail call optimization,a tail recursive function will only ever open a constant number of frames
Tail Recursion ● An expression in a tail context is evaluated as the last step the function call ○ That means nothing is evaluated/applied after it is evaluated ● Function calls in a tail context are called tail calls ● If all recursive calls are in tail contexts, we say that function is tail recursive ○ If a language supports tail call optimization, a tail recursive function will only ever open a constant number of frames
Writing Tail Recursive Functions (Method I) 1)Identify recursive calls that are not in a tail context.Tail contexts are: o The last body subexpression in a lambda (a function) o The consequent and alternative in a tail context if o All non-predicate sub-expressions in a tail context cond o The last sub-expression in a tail context and,or,begin,or let 2)Create a helper function with arguments to accumulate the computation that prevents it from being tail recursive
Writing Tail Recursive Functions (Method I) 1) Identify recursive calls that are not in a tail context. Tail contexts are: ○ The last body subexpression in a lambda (a function) ○ The consequent and alternative in a tail context if ○ All non-predicate sub-expressions in a tail context cond ○ The last sub-expression in a tail context and, or, begin, or let 2) Create a helper function with arguments to accumulate the computation that prevents it from being tail recursive
Demo Example:Length of Linked List Goal:Write a function that takes in a list and returns the length of the list.Make sure it is tail recursive. (define (length 1st) (define (length-tail lst) (if(nu11？1st) 0 (1 (1ength (cdr 1st))))) scm> (1 ength‘() 0 scm>(1 ength‘(12(34) 3
Example: Length of Linked List Goal: Write a function that takes in a list and returns the length of the list. Make sure it is tail recursive. (define (length lst) (if (null? lst) 0 (+ 1 (length (cdr lst))))) scm> (length ‘()) 0 scm> (length ‘(1 2 (3 4)) 3 (define (length-tail lst) ) Demo