CODEWITHSUNDEEP
functional-programmingscheme
user1299108
user1299108

Reputation: 25

Tail Recursive counting function in Scheme

The function is supposed to be tail-recursive and count from 1 to the specified number. I think I'm fairly close. Here's what I have:

(define (countup l)
  (if (= 1 l) 
      (list l)
      (list
       (countup (- l 1))
       l
       )
    )
  )

However, this obviously returns a list with nested lists. I've attempted to use the append function instead of the second list to no avail. Any guidance?

Upvotes: 1

Views: 2127

Answers (4)

Óscar López
Óscar López

Reputation: 236122

You should use an auxiliar function for implementing a tail-recursive solution for this problem (a "loop" function), and use an extra parameter for accumulating the answer. Something like this:

(define (countup n)
  (loop n '()))

(define (loop i acc)
  (if (zero? i)
      acc
      (loop (sub1 i) (cons i acc))))

Alternatively, you could use a named let. Either way, the solution is tail-recursive and a parameter is used for accumulating values, notice that the recursion advances backwards, starting at n and counting back to 0, consing each value in turn at the beginning of the list:

(define (countup n)
  (let loop ((i n)
             (acc '()))
    (if (zero? i)
        acc
        (loop (sub1 i) (cons i acc)))))

Upvotes: 1

twf
twf

Reputation: 325

Assuming this is for a learning exercise and you want this kind of behaviour:

(countup 5) => (list 1 2 3 4 5)

Here's a hint - in a tail-recursive function, the call in tail position should be to itself (unless it is the edge case).

Since countup doesn't take a list of numbers, you will need an accumulator function that takes a number and a list, and returns a list.

Here is a template:

;; countup : number -> (listof number)
(define (countup l)

  ;; countup-acc : number, (listof number) -> (listof number)
  (define (countup-acc c ls)
    (if ... 
        ...
        (countup-acc ... ...)))

  (countup-acc l null))

In the inner call to countup-acc, you will need to alter the argument that is checked for in the edge case to get it closer to that edge case, and you will need to alter the other argument to get it closer to what you want to return in the end.

Upvotes: 0

Matt
Matt

Reputation: 10833

Here a working version of your code that returns a list in the proper order (I replaced l by n):

(define (countup n)
 (if (= 1 n) 
     (list n)
     (append (countup (- n 1)) (list n))))

Sadly, there is a problem with this piece of code: it is not tail-recursive. The reason is that the recursive call to countup is not in a tail position. It is not in tail position because I'm doing an append of the result of (countup (- l 1)), so the tail call is append (or list when n = 1) and not countup. This means this piece of code is a normal recusrive function but to a tail-recursive function.

Check this link from Wikipedia for a better example on why it is not tail-recusrive.

To make it tail-recursive, you would need to have an accumulator responsible of accumulating the counted values. This way, you would be able to put the recursive function call in a tail position. See the difference in the link I gave you.

Don't hesitate to reply if you need further details.

Upvotes: 0

Matt Fenwick
Matt Fenwick

Reputation: 49105

Here's an incorrect solution:

(define (countup n)
  (define (help i)
    (if (<= i n)
        (cons i (help (+ i 1)))
        '()))
  (help 1))

This solution:

  • uses a helper function
  • recurses over the numbers from 1 to n, cons-ing them onto an ever-growing list

Why is this wrong? It's not really tail-recursive, because it creates a big long line of cons calls which can't be evaluated immediately. This would cause a stack overflow for large enough values of n.

Here's a better way to approach this problem:

(define (countup n)
  (define (help i nums)
    (if (> i 0)
        (help (- i 1)
              (cons i nums))
        nums)))
  (help n '()))

Things to note:

  • this solution is better because the calls to cons can be evaluated immediately, so this function is a candidate for tail-recursion optimization (TCO), in which case stack space won't be a problem.
  • help recurses over the numbers backwards, thus avoiding the need to use append, which can be quite expensive

Upvotes: 1

Related Questions