schemeracket

Dr Racket Recursing Without Returning Inital Parent Node Within Function


So I have the function ancestors-names which takes an argument pers from a structure list and attempts to return all of the names of family members occurring within that structure. The intitial structure looks as follows.

struct human (name parent-1 parent-2)
(define (ancestors-names pers)
  (if (empty? pers)
      '()
      (cons (human-name pers)
            (append (ancestors-names (human-parent-1 pers))
                    (ancestors-names (human-parent-2 pers))))))

However next i'm to do the same thing recursively without using the initial pers or in other words i'm supposed to return a list of all ancestors of a name without including that first name in the list. What i'm having trouble understanding is how to do this without using the initial node or name to originally recurse upon.

(define (my-ancestors-names pers)
  (if (empty? pers)
      '()
      leaving out or altering -> (cons (human-name pers)
            (append (my-ancestors-names (human-parent-1 pers))
                    (my-ancestors-names (human-parent-2 pers))))))

i've attempted to use the (human-name(human-parent-1) int the cons statement however the obvious issue with that is that both trees are needed and it simply returns an empty list.

I've tried just taking the recursive function without (cons (human-name pers) leaving only the append statement however this doesnt allow for the construction of the list of names and only returns a blank list.


Solution

  • First, write down who the ancestors of a person are.
    They are

    • The two parents, and
    • The ancestors of those parents.

    This is straightforward to translate into Scheme:

    (define (ancestors pers)
      (if (empty? pers)
          '()
          (cons (human-parent-1 pers)
                (cons (human-parent-2 pers)
                      (append (ancestors (human-parent-1 pers))
                              (ancestors (human-parent-2 pers)))))))
    

    or

    (define (ancestors pers)
        (if (empty? pers)
                '()
            (let ([parent-1 (human-parent-1 pers)]
                  [parent-2 (human-parent-2 pers)])
                (append (list parent-1 parent-2)
                        (ancestors parent-1)
                        (ancestors parent-2)))))
    

    Then you can extract the names,

    (define (ancestors-names pers) (map human-name (ancestors pers)))