CODEWITHSUNDEEP
listrecursionschemeracketradix
Adam Spencer Baker
Adam Spencer Baker

Reputation: 53

Using recursion to getNth position for Racket

I have to write a recursive call in Racket that allows us to get the Nth position of a given list. for example (getNth 3 '(1 2 3 4)) should return back 4 and if the list is empty or if the position is non existent then return and empty list.

this is my code: 

(define getNth
   (lambda (ls)
     (if (= ls null?) 1
         (getNth ls(append '(car ls)(cdr ls))))))

getting this error: getnth: arity mismatch; the expected number of arguments does not match the given number expected: 1 given: 2 arguments...: 4 ()

if you need the recursive statement here it is:

base case-getNth N LS) = (), if LS = null

recursive call -(getNth N LS) = (getNth N (append '(car LS)(cdr LS))), if N >= 1

im getting stumped I dont know how to implement this one.

Upvotes: 0

Views: 2760

Answers (2)

Sebastien
Sebastien

Reputation: 1476

Assuming your getNth can revieve a "N" from a list (rather than a fixed N i.e. get3rd), your are indeed missing an argument:

(define getNth                     
   (lambda (n list)                   
      (cond ((null? list) '())             
            ((= n 0) (car list))              
            (else (getNth (- n 1) (cdr list))))))

Which basically is until I get to the number I want, decrement the it and "pop" the first element out until the first element of the list is the one I want i.e. the rest of the list.

Your lambda only takes one argument the way you defined it which is exactly the error message you're having ;)

I think I appropriately balanced my parenthesis :)

A trick with recursion: it's generic concept is easy:

A recusrion is "if a terminal condition occurs, I'm done, return appropriate value. Else, increment the argument toward termination condition and call myself with these new arguments"

It gets complicated when the termination condition can have exceptions. Because if your can't trivially expressed it as "if this done else redo with increment" you could make mistakes...

Upvotes: 1

Sylwester
Sylwester

Reputation: 48775

There are several issues with you code..

  1. You say you need a procedure that takes two arguments, but yours take only ls.
  2. When ls is the empty list the result is 1
  3. if list is not empty you recurse with two arguments, both lists. The first is the same as the original argument which would make a infinite recursion. The second is an append between '(car lst) which evaluates to the list (car lst) and (cdr ls) (the the list ls except the first pair)
(define get-nth
  (lambda (index lst)
    (if (= index 0)            ; when index is zero
        (car lst)              ; return the first element
        (get-nth (- index 1)   ; else recurse with the decrement of index
                 (cdr lst))))) ; and all but the first element (the rest) of lst

;; test
(get-nth 0 '(a))   ; ==> a
(get-nth 1 '(a b)) ; ==> b

;; However, this won't work:
(get-nth 0 '())       ; will fail
(get-nth 10 '(a b c)) ; will fail

I kind of like the fact that it doesn't work when given wrong arguments. list-ref and car fails just as much if gived wrong parameters, but that is easy to fix:

(define get-nth
  (lambda (index lst)
    (cond ((not (pair? lst)) '())        ; it should always be a pair
          ((= index 0) (car lst))        ; when index is zero, return the first element
          (else (get-nth (- index 1)     ; else recurse with the decrement of index
                         (cdr lst))))))  ; and all but the first element (the rest) of lst

Instead of just th empty list you can have a default value or perhaps throw an error with (raise 'get-nth-error) (R6RS+)

Upvotes: 1

Related Questions