Call Trees
fun s u m l i s t n i l = 0 | s u m l i s t ( x : : xs ) = x + s u m l i s t xs
(Tail) Recursion Amtoft from Hatcli Run-Time Structures Accumulators Tail Recursion Further Examples Summary
has a linear call-tree
sum list ([2 ,1]) | sum list ([1]) | sum list ( nil ) fun f i b 0 = 0 | fib 1 = 1 | f i b n = f i b ( n1) + f i b ( n2)
has a non-linear (branching) call-tree
f i b (3) / \ f i b (2) f i b (1) / \ f i b (0) f i b (1)
Stacking Bindings
fun r e v e r s e n i l = n i l | r e v e r s e ( x : : xs ) = r e v e r s e xs @ [ x ] val L = [ 1 , 2 , 3 ] ; reverse (L ) ;
(Tail) Recursion Amtoft from Hatcli Run-Time Structures Accumulators Tail Recursion Further Examples Summary
Environment during recursion: (see p. 67)
++ | | ++ | xs nil | | x 3 | ++ | xs [3] | | x 2 | ++ | xs [2 ,3] | | x 1 | ++ | L [1 ,2 ,3] | | ... | ++ . . added i n r e v e r s e ( n i l )
. . added i n r e v e r s e ( [ 3 ] )
. . added i n r e v e r s e ( [ 2 , 3 ] )
. . added i n r e v e r s e ( [ 1 , 2 , 3 ] )
. . top l e v e l environment
Running Time
(Tail) Recursion Amtoft from Hatcli Run-Time Structures Accumulators Tail Recursion Further Examples
fun r e v e r s e n i l = n i l | r e v e r s e ( x : : xs ) = ( r e v e r s e xs ) @ [ x ]
Summary
Consider calling reverse on a list of length n
it makes n calls to append which takes time 1, 2, . . . n 2, n 1, n
the running time is thus quadratic.
Performance Test
We need generator of large data:
fun from i j = i f i > j then n i l e l s e i : : from ( i +1) j
(Tail) Recursion Amtoft from Hatcli Run-Time Structures Accumulators Tail Recursion Further Examples Summary
Execute reverse L where L is the value of (from 1 n) n 10,000 20,000 40,000 100,000 running time 2 seconds 7 seconds 34 seconds very slow
When testing sum list, we rather want
fun o n e s 0 = n i l | o n e s n = 1 : : o n e s ( n1)
Assessment
(Tail) Recursion Amtoft from Hatcli Run-Time Structures Accumulators Tail Recursion
fun r e v e r s e n i l = n i l | r e v e r s e ( x : : xs ) = ( r e v e r s e xs ) @ [ x ]
Further Examples Summary
Why must we call append? :: only allows us to add items in front of list reverse does non-trivial computation only when going up the tree We might consider doing computation when going down the tree
Passing Results Down In Call Tree
Recall that list reversal is special case of foldl
fun f o l d l f e n i l = e | f o l d l f e ( x : : xs ) = f o l d l f ( f (x , e )) xs fun m y r e v e r s e x s = f o l d l op : : n i l xs ;
(Tail) Recursion Amtoft from Hatcli Run-Time Structures Accumulators Tail Recursion Further Examples Summary
Specializing foldl wrt op:: yields
fun r e v a c c e n i l = e | rev acc e ( x : : xs ) = rev acc ( x : : e ) xs fun r e v e r s e a c c x s = r e v a c c n i l x s
e holds the results so far e is owing down the tree, informing the recursion at the next level of something that we have accumulated at the current level
Performance Comparison
(Tail) Recursion Amtoft from Hatcli Run-Time Structures Accumulators
Recall that reverse had quadratic running time. Since reverse acc uses no append, we expect linear running time. When called on the value of from 1 n n 10,000 20,000 100,000 1,000,000 reverse 2 seconds 7 seconds very slow infeasible reverse acc instantaneous instantaneous instantaneous 3 seconds
Tail Recursion Further Examples Summary
Tail Recursion
(Tail) Recursion Amtoft from Hatcli Run-Time Structures Accumulators Tail Recursion
fun r e v a c c e n i l = e | rev acc e ( x : : xs ) = rev acc ( x : : e ) xs
Further Examples Summary
This function is tail recursive: no computation happens after the recursive call value of recursive call is the return value thus, no variables are referenced after recursive call This kind of recursion is actually iteration in disguise!
Iterative Reverse
fun r e v a c c e n i l = e | rev acc e ( x : : xs ) = rev acc ( x : : e ) xs
(Tail) Recursion Amtoft from Hatcli Run-Time Structures Accumulators Tail Recursion
can be converted to pseudo-C (renaming e to acc):
l i s t r e v e r s e ( xs : l i s t ) { l i s t acc ; acc = [ ] ; w h i l e ( x s != n i l ) do { a c c = hd ( x s ) : : a c c ; xs = t l ( xs ) ; } return acc ; }
Further Examples Summary
acc holds result xs and acc are updated each time through the loop
Tail Recursion versus Non-Tail Recursion
( v e r s i o n 1 : without accumulator ) fun r e v e r s e n i l = n i l | r e v e r s e ( x : : xs ) = r e v e r s e xs @ [ x ] ( v e r s i o n 2 : with accumulator ) fun r e v a c c e n i l = e | rev acc e ( x : : xs ) = rev acc ( x : : e ) xs
(Tail) Recursion Amtoft from Hatcli Run-Time Structures Accumulators Tail Recursion Further Examples Summary
x is used after recursion in v.1, but not in v.2 for tail-recursive functions, we do thus not need to stack variable bindings for the recursive calls parameter passing can be implemented in the compiler by destructive updates (that is, assignment)! Computation occurs after recursion in v.1, but not in v.2 for tail-recursive functions, we do thus not need to stack return addresses; a call can be implemented in the compiler as a goto!
Parameter Assignment
The tail-recursive function
fun f ( y 1 , . . . , y n ) = ... f (<exp 1>, . . . , <expn>)
(Tail) Recursion Amtoft from Hatcli Run-Time Structures Accumulators Tail Recursion Further Examples Summary
...is roughly equivalent to...
... f(y 1 , ... , y n) { while . . . { ... ... y 1 = <exp 1>; ... y n = <expn >; } }
Converting SumList to Tail Recursion
fun s u m l i s t n i l = 0 | s u m l i s t ( x : : xs ) = x + s u m l i s t xs
(Tail) Recursion Amtoft from Hatcli Run-Time Structures Accumulators
The recursive calls are unfolded until we reach the end of the list, from where we then move to the left while summing the results.
fun s u m l i s t a c c a c c n i l = a c c | s u m l i s t a c c acc ( x : : xs ) = s u m l i s t a c c ( x+a c c ) x s
Tail Recursion Further Examples Summary
Summation proceeds while moving left to right. Top-level call: sum list acc 0 xs Performance comparison on the value of ones n n 4,000,000 5,000,000 sum list 5 seconds 21 seconds sum list acc instantaneous instantaneous
Tail-Recursive MultList
fun m u l t l i s t a c c a c c n i l = a c c | m u l t l i s t a c c acc ( x : : xs ) = m u l t l i s t a c c ( x acc ) xs
(Tail) Recursion Amtoft from Hatcli Run-Time Structures Accumulators Tail Recursion Further Examples Summary
Question: what happens if we hit a 0?
fun m u l t l i s t a c c e x i t a c c n i l = a c c | m u l t l i s t a c c e x i t acc ( x : : xs ) = i f x = 0 then 0 e l s e m u l t l i s t a c c e x i t ( x acc ) xs
In C, we might have
int m u l t l i s t ( xs : l i s t ) { i n t acc ; acc = 1 ; w h i l e ( x s != n i l ) do { i f ( hd ( x s ) = 0 ) t h e n return 0; / e s c a p e / else a c c = hd ( x s ) a c c ; xs = t l ( xs ) ; } r e t u r n acc ;
Making Fibonacci Tail-Recursive
fun f i b 0 = 0 | fib 1 = 1 | f i b n = f i b ( n2) + f i b ( n1)
(Tail) Recursion Amtoft from Hatcli Run-Time Structures Accumulators Tail Recursion Further Examples Summary
has a branching call-tree, and can be made tail-recursive by using two accumulating parameters:
fun f i b a c c p r e v c u r r n = i f n = 1 then c u r r e l s e f i b a c c c u r r ( p r e v+c u r r ) ( n1) fun f i b o n a c c i a c c n = i f n = 0 then 0 e l s e f i b a c c 0 1 n
Performance comparison n 42 43 44 fib 7 seconds 11 seconds 17 seconds fibonacci acc instantaneous instantaneous instantaneous
Correctness of Tail-Recursive Fibonacci
With F the bonacci function we have
F (0) = 0; F (1) = 1; F (n) = F (n 2) + F (n 1)
(Tail) Recursion Amtoft from Hatcli Run-Time Structures Accumulators Tail Recursion Further Examples
which can be tail-recursively implemented by
fun g ( n , p r e v , c u r r ) = i f n = 1 then c u r r e l s e g ( n 1, c u r r , p r e v+c u r r )
Summary
Correctness Lemma: for all n 1, k 0: g (n, F (k), F (k + 1)) = F (n + k) This can be proved by induction in n. the base case is n = 1 which is obvious. for the inductive case, n > 1,
g (n, F (k), F (k+1)) = g (n1, F (k+1), F (k)+F (k+1)) = g (n1, F (k+1), F (k+2)) = F ((n1)+(k+1)) = F (n+k)
Thus F (n) = g (n, F (0), F (1)) = g (n, 0, 1).
Summary
(Tail) Recursion Amtoft from Hatcli Run-Time Structures Accumulators
a tail-recursive function is one where the function performs no computation after the recursive call a good SML compiler will detect tail-recursive functions and implement them iteratively
as loops there is no need to stack bindings or return addresses recursive calls become gotos we can think of arguments as being assigned to (destructively update) formal parameters.
Tail Recursion Further Examples Summary
this substantially reduces execution time and space (for stack) overhead
