CODEWITHSUNDEEP
racket
Sp1DeR
Sp1DeR

Reputation: 29

racket. Implement the Ackermann's function

I'm trying to understand, but so far I can not make myself. When I see the finished solution is easier to understand how to do it. This is my first exercise, the others want to do it myself, but need to understand how to implement it. Please help me how to write a racket function.

Implement the Ackermann's function A. It takes two parameters, x and y, and works as follows:

if y = 0, then it returns 0;
if x = 0, then it returns 2*y;
if y = 1, then it returns 2;
else, it calls itself (function A) with x = x-1 and y = A ( x, (y - 1) )

The project is given

#lang racket/base

(require rackunit)

;; BEGIN

;; END

(check-equal? (A 1 10) 1024)
(check-equal? (A 2 4) 65536)
(check-equal? (A 3 3) 65536)

Upvotes: 1

Views: 837

Answers (2)

soegaard
soegaard

Reputation: 31147

Here is one solution:

#lang racket

(define (ack x y)
  (match* (x y)
    [(_ 0) 0]       ; if y = 0, then it returns 0
    [(0 y) (* 2 y)] ; if x = 0, then it returns 2*y
    [(_ 1) 2]       ; if y = 1, then it returns 2
    [(x y) (ack (- x 1) (ack x (- y 1)))]))

Upvotes: 1

Óscar López
Óscar López

Reputation: 236004

It's a straightforward translation, you just have to write the formula using Scheme's syntax:

(define (A x y)
  (cond ((= y 0) 0)       ; if y = 0, then it returns 0
        ((= x 0) (* 2 y)) ; if x = 0, then it returns 2*y
        ((= y 1) 2)       ; if y = 1, then it returns 2
        (else (A (- x 1)  ; else it calls itself (function A) with x = x-1
                 (A x (- y 1)))))) ; and y = A ( x, (y - 1))

Upvotes: 1

Related Questions