Introduction to Artificial Intelligence
Worksheet 2, Recursion
Recursion exercises - all problems to be solved recursively
-
Without using the Lisp primitive nthcdr, write a procedure called TrimFirst
that trims off the first n elements from a list.
Example: (TrimFirst 4 '(a b c d e f g h i j)) returns (e f g h i j)
-
Write a procedure KeepFirst that will return the first n elements of a list.
It should be tail recursive.
Example: (KeepFirst 5 '(a b c d e f g h)) returns (a b c d e)
-
Write an efficient version of Fibonacci which is not as inefficient as the one
shown in the book. Use optional parameters and think of working forward
from the first month.
- Insertion Sort
- Part A. Write a procedure called Ins which will insert a number in an already
sorted
list. Example: (Ins '4 '(1 2 5 8)) returns (1 2 4 5 8)
- Part B. Write a procedure called InSort (which uses Ins above) which takes
an unordered
list as a parameter and returns an ordered list.
Example: (InSort '(3 1 5 4 7 2 9)) returns (1 2 3 4 5 7 9)
-
Write a function Presentp which will determine if a given atom occurs anywhere
in the list, even in the sublists.
Example: (Presentp 'x '((a b)(w x)(1 3))) returns T