CSE505 Problem3-recursive definitions into tail-recursive Solved

Description

3  Convert the following recursive definitions into tail-recursive definitions.

1. fun f(1) = 1

| f(n) = n*n  +  f(n-1);          (* assume n > 1 *)

Name the tail-recursive function as f2.

1. fun flatten([ ]) = [ ]

|  flatten(h::t)  = h @ flatten(t);

Name the tail-recursive function as flatten2.

1. datatype ‘a tree = leaf of ‘a | node of ‘a tree * ‘a tree;

fun cat(leaf(s)) = s

| cat(node(t1, t2)) = cat(t1) ^ “ “ ^ cat(t2);

Name the tail-recursive function as cat2.

How to run ML on Timberlake   (you may also install and run ML on your personal computer)

Place all function definitions in one file, called A2_Problem3.sml.  Run the program as follows.

 

timberlake% /util/bin/sml  A2_Problem3.sml

• f(5);
• f2(5);                                         (* should give same answer as f(5)  *)

–

• flatten( [[1,2], [3,4,5], [ ], [6,7,8]] );
• flatten2( [[1,2], [3,4,5], [ ], [6,7,8]] ); (* should give same answer as flatten  *)

–

• … similarly test cat and cat2 – use the tree shown in Lecture 14 slide 15 …
• Ctrl-d to exit