Theme index -- Keyboard shortcut: 'u'  Previous theme in this lecture -- Keyboard shortcut: 'p'  Next slide in this lecture -- Keyboard shortcut: 'n'Name binding, Recursion, Iteration, and Continuations
11.  Recursion and iteration

Recursion plays an important role for non-trivial functional programs. One of the reasons is that recursive data structures are used heavily in functional programs. Just take, as example, linear lists, cf. Chapter 6.

As another reason, most non-trivial needs some kinds of repeating structures - iteration. In our style of Scheme programming, we use recursive functions for iterative purposes. In this chapter we will see how this can be done without excessive use of memory resources.

And as before we attempt to illustrate also this topic with examples from the web domain.

11.1 Recursion11.5 Recursion versus iteration
11.2 List processing11.6 Example of recursion: number-interval
11.3 Tree processing (1)11.7 Examples of recursion: string-merge
11.4 Tree processing (2)11.8 Examples with recursion: string-of-char-list?
 

11.1.  Recursion
Contents   Up Previous Next   Slide    Subject index Program index Exercise index 

In this section we characterize the basic ideas of recursion, and the kinds of problem solving which are aided by recursion.

Recursive functions are indispensable for the processing of recursive data structures

Recursion is an algorithmic program solving idea that involves solution of subproblems of the same nature as the overall problem

  • Given a problem P

    • If P is trivial then solve it immediately

    • If P is non-trivial, divide P into subproblems P1 ,..., Pn

    • Observe if Pi (i=1..n) are of the same nature as P

    • If so, use the overall problem solving idea on each of P1 ... Pn

    • Combine solutions of the subproblems P1 ... Pn to a solution of the overall problem P

We would like to refer the reader to an ECIU material on recursion, which in a more careful way discusses and illustrates the ideas [eciu-recursion]. Notice that there is some overlap with the ECIU material and the material you are reading now.

 

11.2.  List processing
Contents   Up Previous Next   Slide    Subject index Program index Exercise index 

We have already discussed lists as a recursive data type in Section 6.1. In this section we will give an extended LAML related example of recursive list processing in Scheme.

A list is a recursive data structure

As a consequence list processing is done via recursive functions

We illustrate list processing by extracting attribute values from a LAML attribute property list

The function find-href-attribute in Program 11.1 extracts the href attribute value from an attribute property list. Property lists have already been discussed in Section 6.6.

Notice the recursive nature of the function find-href-attribute. The recursive call is highlighted with red color.

It happens to be the case that the function in Program 11.1 is tail recursive, cf. the discussion in Section 11.5.

1
2
3
4
5
6
7
8
9
10
11
12
13
; Return the href attribute value from a property list
; Return #f if no href attribute is found.
; Pre-condition: attr-p-list is a property list - 
; of even length.  
(define (find-href-attribute attr-p-list)
 (if (null? attr-p-list)
     #f
     (let ((attr-name (car attr-p-list))
           (attr-value (cadr attr-p-list))
           (attr-rest (cddr attr-p-list)))
      (if (eq? attr-name 'href)
          attr-value
          (find-href-attribute attr-rest)))))
Program 11.1    A function for extraction of the href attribute from a property list.

To stay concrete, we show an example of using the function find-href-attribute in Program 11.2.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
1> (define a-clause 
    (a 'id "myid" 'class "myclass" 'href "http://www.cs.auc.dk"))

2> a-clause
(ast "a" () 
  (id "myid" class "myclass" href "http://www.cs.auc.dk" 
   shape "rect") 
  double xhtml10-strict)

3> (render a-clause)
"<a id = \"myid\" class = \"myclass\" 
    href = \"http://www.cs.auc.dk\"></a>"

4> (define attr-list (ast-attributes a-clause))

5> attr-list
(id "myid" class "myclass"
 href "http://www.cs.auc.dk" shape "rect")

6> (find-href-attribute attr-list)
"http://www.cs.auc.dk"  
>
Program 11.2    An example with property lists that represent HTML attributes in LAML.

 

11.3.  Tree processing (1)
Contents   Up Previous Next   Slide    Subject index Program index Exercise index 

Trees are another classical example of recursive data types.

In this section we show a web document and its internal structure. In Section 11.4 we show how to traverse this document, by means of tree traversal, with the purpose of extracting and collecting all URLs from href attributes of anchor elements in the document.

A tree is a recursive data structure

We illustrate how to extract information from an HTML syntax tree

The LAML document in Program 11.3 shows a web document, in which we have highlighted all the anchor elements - the a elements. The tree structure in Figure 11.1 shows the hierarchical composition of the document, in terms of HTML elements. In the web version of the material - slide or annotated slide view - you can also access the actual abstract syntax tree - AST - which is the internal document representation of LAML. We do not include it in this version of the material because it is relatively long.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
(load (string-append laml-dir "laml.scm"))
(laml-style "simple-xhtml1.0-strict-validating")

(write-html '(prolog pp)
(html
 (head (title "Demo Links"))
 (body
  (p "ACM has a useful"
     (a 'href "http://www.acm.org/dl" "digital library") )
  (p "The following places are also of interest:")

  (ul
   (li (a 'href "http://www.ieee.org/ieeexplore/" "The IEEE"))
   (li "The" (a 'href "http://www.w3c.org" "W3C") "site")
   (li 
    (a 'href "http://link.springer.de/link/service/series/0558/" 
       "Lecture Notes in Computer Science")))

  (p "Kurt NÝrmark" (br) 
     (a 'href "http://www.cs.auc.dk" "Dept. of Comp. Science") 
     (br)
     (a 'href "http://www.auc.dk" "Aalborg University")))))

(end-laml)
Program 11.3    A sample web document with a number of links.

Figure 11.1    The syntax tree of the web document with the root made up by the html element.

 

11.4.  Tree processing (2)
Contents   Up Previous Next   Slide    Subject index Program index Exercise index 

We continue the example from Section 11.3 .

In Program 11.4 we show the function extract-links . The function is indirectly recursive via the function extract-links-ast-list .

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
; Return a list of URLS as located in the a elements of ast.  
(define (extract-links ast)
 (if (ast? ast)
     (let ((name (ast-element-name ast))
           (subtrees (ast-subtrees ast))
          )
       (if (equal? name "a")
           (let ((href-attr-value 
                  (find-href-attribute (ast-attributes ast))))
             (if href-attr-value (list href-attr-value) '()))
           (extract-links-ast-list subtrees)))
     '()))

; Return a list of URLS as located in the a elements of 
; the list of ast's as passed in ast-list.  
(define (extract-links-ast-list ast-list)
 (if (null? ast-list)
     '()
     (append 
      (extract-links (car ast-list))
      (extract-links-ast-list (cdr ast-list)))))
Program 11.4    The link extraction functions.

The extract-links function above traverses the internal AST structure of a web document. When an anchor element is encountered, when (equal? name "a") becomes true, we collect the href attribute by means of the function find-href-attribute, which we described in Section 11.2, see Program 11.1. In the cases where we do not encounter an anchor element, the call (extract-links-ast-list subtrees) causes traversal of the list of subtrees.

In the dialogue shown below we illustrate how to extract the URLs from a demo document, which we assume is identical with the document in Program 11.3.

1
2
3
4
5
6
7
8
9
10
1> (define doc-ast 
    (html
     (head (title "Demo Links"))
     (body
       ...)))

2 > (extract-links doc-ast)
("http://www.acm.org/dl" "http://www.ieee.org/ieeexplore/" "http://www.w3c.org"
 "http://link.springer.de/link/service/series/0558/" "http://www.cs.auc.dk"
 "http://www.auc.dk")
Program 11.5    A link extraction dialogue.


Exercise 3.2. The function outline-copy

Program a function outline-copy which makes a deep copy of a list structure. Non-list data in the list should all be translated to a symbol, such as '-. You should be able to handle both proper lists and improper lists.

As an example:

  (outline-copy '((a b c) (d e . f) (h i))) =>
     ((- - -) (- - . -) (- -))
Solution


 

11.5.  Recursion versus iteration
Contents   Up Previous Next   Slide    Subject index Program index Exercise index 

The purpose of this section is to introduce and not least motivate the idea of tail recursion.

Recursive functions are - modulo use of memory resources - sufficient for any iterative need

Tail recursive functions in Scheme are memory efficient for programming of any iterative process

Tail recursion is a variant of recursion in which the recursive call takes place without contextual, surrounding calculations in the recursive function.

A tail call is the last 'thing' to be done before the function returns. Therefore there is no need to maintain any activation record of such a recursive call - we can reuse the callers activation record.

The main source of insight to understand tail recursiveness is a series of images, which are available in the web version of the material (slide view). You should definitively consult this before you go on in this material.

 

11.6.  Example of recursion: number-interval
Contents   Up Previous Next   Slide    Subject index Program index Exercise index 

We provide an example of a recursive function, namely number-interval.

The function number-interval returns a list of integers from a lower bound to an upper bound

The version of number-interval shown in Program 11.6 is not tail recursive. The rewriting of the function in Program 11.7 is tail recursive however. Notice that the function in Program 11.7 needs a helping function, number-interval-iter-help, with an appropriate parameter profile.

1
2
3
4
(define (number-interval f t)
 (if (<= f t)
     (cons f (number-interval (+ f 1) t))
    '()))
Program 11.6    The function number-interval from the general LAML library.

1
2
3
4
5
6
7
8
(define (number-interval-iter f t)
  (reverse (number-interval-iter-help f t '())))


(define (number-interval-iter-help f t res)
  (if (<= f t)
      (number-interval-iter-help (+ f 1) t (cons f res))
      res))
Program 11.7    The function number-interval-iter is an iterative, tail recursive variant of number-interval.

We show below a couple of concrete applications of the functions in Program 11.6 and Program 11.7.

1
2
3
4
5
6
7
8
1> (number-interval 1 10)
(1 2 3 4 5 6 7 8 9 10)

2> (number-interval-iter 10 20)
(10 11 12 13 14 15 16 17 18 19 20)

3> (number-interval-iter 20 10)
()
Program 11.8    A sample dialogue with the number interval functions.


Exercise 3.3. The append function

The function append, which is a standard Scheme function, concatenates two or more lists. Let us here show a version which appends two lists:

  (define (my-append lst1 lst2)
       (cond ((null? lst1) lst2)
             (else (cons (car lst1) (my-append (cdr lst1) lst2)))))

We will now challenge ourselves by programming an iterative solution, by means of tail recursion. We start with the standard setup:

  (define (my-next-append lst1 lst2)
    (my-next-append-1 lst1 lst2 ...))

where my-next-append-1 is going to be the tail recursive function:

  (define (my-next-append-1 lst1 lst2 res)
    (cond ((null? lst1) ...)
          (else (my-next-append-1 (cdr lst1) lst2 ...))))

Fill out the details, and try out your solution.

Most likely, you will encounter a couple of problems! Now, do your best to work around these problems, maybe by changing aspects of the templates I have given above.

One common problem with iterative solutions and tail recursive functions is that lists will be built in the wrong order. This is due to our use of cons to construct lists, and the fact that cons operates on the front end of the list. The common medicine is to reverse a list, using the function reverse, either on of the input, or on the output.

Solution


Exercise 3.4. A list replication function

Write a tail recursive function called replicate-to-length, which in a cyclic way (if necessary) replicates the elements in a list until the resulting list is of certain exact length. The following serves as an example:

        (replicate-to-length '(a b c) 8) =>
        (a b c a b c a b)
        (replicate-to-length '(a b c) 2) =>
        (a b)
      

In other words, in (replicate-to-length lst n), take elements out of lst, cyclically if necessary, until you reach n elements.

Solution


 

11.7.  Examples of recursion: string-merge
Contents   Up Previous Next   Slide    Subject index Program index Exercise index 

This section and the next give yet other examples of recursive functions. We start with string-merge.

The function string-merge zips two lists of strings to a single string. The lists are not necessarily of equal lengths

1
2
3
4
5
6
(define (string-merge str-list-1 str-list-2)
 (cond ((null? str-list-1) (apply string-append str-list-2))
       ((null? str-list-2) (apply string-append str-list-1))
       (else (string-append
              (car str-list-1) (car str-list-2)
              (string-merge (cdr str-list-1) (cdr str-list-2))))))
Program 11.9    The recursive function string-merge.

The function in Program 11.9 not tail recursive. To remedy this weakness, we make another version which is. It is shown in Program 11.10.

As it is characteristic for all tail recursive functions, the state of the iteration needs to be represented in the parameter list, here in the helping function called merge-iter-helper. The necessary state for string merging purpose is reduced to the resulting, merged string - the res parameter.

1
2
3
4
5
6
7
8
9
10
11
12
13
(define (string-merge-iter str-list-1 str-list-2)
 (merge-iter-helper  str-list-1 str-list-2 ""))

(define (merge-iter-helper str-list-1 str-list-2 res)
 (cond ((null? str-list-1) 
          (string-append res (apply string-append str-list-2)))
       ((null? str-list-2) 
          (string-append res (apply string-append str-list-1)))
       (else (merge-iter-helper
                (cdr str-list-1) 
                (cdr str-list-2)
                (string-append 
                    res (car str-list-1) (car str-list-2))))))
Program 11.10    A tail recursive version of string-merge.

In the LAML software, the function string-merge is used in several contexts. One of them is in the function list-to-string , which we show in Program 11.11 We could in fact have applied list-to-string in the function as-string, which we discussed in Program 10.4.

1
Program 11.11    An application of string-merge which converts a list of strings to a string with a given separator.

 

11.8.  Examples with recursion: string-of-char-list?
Contents   Up Previous Next   Slide    Subject index Program index Exercise index 

The last example in this chapter is a boolean function that can check if a string is formed by the characters from a given alphabet.

The function string-of-char-list? is a predicate (a boolean function) that finds out if a string is formed exclusively by characters from a particular alphabet.

1
2
3
4
5
6
7
8
(define (string-of-char-list? str char-list)
  (string-of-char-list-1? str char-list 0 (string-length str)))

(define (string-of-char-list-1? str char-list i lgt)
  (if (= i lgt)
      #t
      (and (memv (string-ref str i) char-list)
           (string-of-char-list-1? str char-list (+ i 1) lgt))))
Program 11.12    The function string-of-char-list? which relies on the tail recursive function string-of-char-list-1?.

The predicates blank-string? and numeric-string? in Program 11.13 are very useful for many practical purposes. The first function checks if a string represents white space only. The latter function checks if a string represents a decimal integer.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
;; A list of characters considered as blank space characters
(define white-space-char-list
   (list #\space (as-char 13) (as-char 10) #\tab))

;; Is the string str empty or blank (consists of white space)
(define (blank-string? str)
  (or (empty-string? str) 
      (string-of-char-list? str white-space-char-list)))

;; Returns if the string str is numeric.
;; More specifically, does str consist exclusively of the
;; ciffers 0 through 9. 
(define (numeric-string? str)
  (string-of-char-list? str 
    (list #\0 #\1 #\2 #\3 #\4 #\5 #\6 #\7 #\8 #\9 )))
Program 11.13    Applications of string-of-char-list?.


Exercise 3.5. Sublists of a list

In this exercise we will program a function front-sublist which returns the first n elements of a list. The signature (the head) of the function should be (front-sublist lst n) where lst is a list and n is a number. As a precondition it can be assumed that lst is a proper list and that n is a non-negative integer. As a postcondition we want to guarantee that the length of the result is n.

As an example

        (front-sublist '(a b c d e) 3)  =>
        (a b c)
      
        (front-sublist '(a b c d e) 6)  =>
        ERROR

First, identify the extreme, border cases and be sure that you know how to handle these. Next, program the function with due respect to both the precondition and the postcondition. Next, test the function carefully in a dialogue with your Scheme system.

Given the function front-sublist we will program the function sublists, which breaks a proper list into a list of sublists of some given size. As an example

        (sublists '(a b c d e f) 3) =>
        ((a b c) (d e f))

Program the function sublists with use of front-sublist. Be careful to prepare you solution by recursive thinking. It means that you should be able to break the overall problem into a smaller problem of the same nature, as the original problem. You should feel free to formulate both preconditions and postconditions of the function sublists, such that the existing function front-sublist fits well.

Hint: The Scheme function list-tail is probably useful when you program the function sublists.

A table can be represented as a list of rows. This is, in fact, the way tables are represented in HTML. The tr tag is used to mark each row; the td tag is used to mark each cell. The table tag is used to mark the overall table. Thus, the list of rows ((a b c) (d e f)) will be marked up as:

         <table>
           <tr> <td>a</td> <td>b</td> <td>c</td> </tr>
           <tr> <td>d</td> <td>e</td> <td>f</td> </tr>
         </table>

Write a Scheme function called table-render that takes a list of rows as input (as returned by the function sublists, which we programmed above) and returns the appropriate HTML rendering of the rows. Use the LAML mirror functions table, tr, and td. Be sure to call the LAML function xml-render to see the textual HTML rendering of the result, as opposed to LAML's internal representation.

Notice: During the course we will see better and better ways to program table-render. Nevertheless, it is a good idea already now to program a first version of it.

There is no solution to this exercise


 

11.9.  References
[Eciu-recursion]Recursion - an ECIU material
http://www.cs.auc.dk/~normark/eciu-recursion/html/recit.html

Generated: Tuesday July 2, 2013, 09:15:17
Theme index -- Keyboard shortcut: 'u'  Previous theme in this lecture -- Keyboard shortcut: 'p'  Next slide in this lecture -- Keyboard shortcut: 'n'