tail recursion again (Scheme)

Question

I implemented tail recursion..since tail recursion is really challenging.. I couldn't figure out clearly.. so the best way, maybe try several implementations until it become clear.. so...here is my code..

tail recursion practice
(define (tstFunc lst1 lst2)
 (define (tstFunc-helper ls1 ls2 rst)
   (if (or (null? ls1) (null? ls2))
       rst
       (tstFunc-help (cdr ls1) (cdr lst2) 
                (cons (tstFunc lst1 lst2) rst)))))

I can't find what is wrong. can someone point out?

Answer 1

Your function is:

(define (tstFunc lst1 lst2)    ;                                           0
  (define (tstFunc-helper      ; helper function                           1
                 ls1           ; its 1st argument  <-----------------\     2
                 ls2           ;     2nd argument  <--------------\  |     3
                 result )      ;     3rd argument                 |  |     4
                                        ;                         |  |     5
     (if (or (null? ls1) (null? ls2))   ;                         |  |     6
        result                          ; return result, OR       |  |     7
        (tstFunc-help                   ; call self with          |  |     8
             (cdr ls1)                  ;   as the next 'ls1' ----|--/     9
             (cdr lst2)                 ;   as the next 'ls2' ----/       10
             (cons                      ;   as the next 'result'          11
                  (tstFunc lst1 lst2)   ; prefix this value (*)           12
                  result)               ;   to current "result", to       13
                                        ;   construct the next "result"   14
             )))                        ;                                 15
                                        ;                                 16
  )

You define a helper function (1), but don't call it (16). A typical initial call will use some initial "result" value, like '() for list construction.

You refer to arguments to the outer function, in your inner function (10,12). It is allowed, just highly probably not what you intended - in particular, lst2 "as the next 'ls2'" won't ever change, will always be the same list.

You're combining your lists (12) at each step by calling the main function (0), creating infinite recursion. You should use some 3rd function to combine them. Usually we combine the cars of our lists, but sometimes the lists themselves are needed too, that's not the problem. But again you're using the wrong argument names there.

Since you build the result by consing (11), you probably want to return the final result (7) reversed back into the original order.

Answer 2

Will's code does not work. He does not call the helper function. Also when he calls it inside the recursion he uses the wrong name. This code does work, although you don't specify what kind or result you want.

 (define (tstFunc lst1 lst2)

  (define (tstFunc-helper      ; helper function
                 ls1           ; its 1st argument  <-----------------\
                 ls2           ;     2nd argument  <--------------\  |
                 result )      ;     3rd argument                 |  |
                                        ;                         |  |
     (if (or (null? ls1) (null? ls2))   ;                         |  |
        result                          ; return result, OR       |  |
        (tstFunc-helper                 ; call self with          |  |
             (cdr ls1)                  ;   as the next 'ls1' ----|--/
             (cdr ls2)                  ;   as the next 'ls2' ----/
             (cons                      ;   as the next 'result'
          (cons ls1 ls2)     ; prefix this value (*)
          result)            ;   to current "result", to
                             ;     construct the next "result"
             )))
  (tstfunc-helper lst1 lst2 '()))`

This is Will's version modified to call the helper function, and with the name fixed. Edit: I fixed the variable names. Didn't see them the first time.