Extremely Deep Recursion - Part 1

Computer Science Level 1

The Ackermann function is a computable function which grows very, very quickly as its inputs grow. For example, while $A(1,2),$ $A (2,2),$ and $A(3,2)$ are equal to $4,7,$ and $29,$ respectively, $A(4,2) \approx 2 \times 10^{19728}$ .

The Ackermann function can be defined as follows: $A(m,n) = \begin{cases} n+1 & \mbox{if } m = 0 \\ A(m-1, 1) & \mbox{if } m > 0 \mbox{ and } n = 0 \\ A(m-1, A(m, n-1)) & \mbox{if } m > 0 \mbox{ and } n > 0. \end{cases}$

What is the value of $A(0,7)?$

Details and assumptions

If you enjoyed this problem, you might also like Part 2 and Part 3 .

The answer is 8.

23 solutions

Thaddeus Abiy
Feb 14, 2014

This was rather easy,but I suspect Parts $2$ and $3$ will be significantly more difficult. Anyways,there are more efficient approaches but a naive recursive function will do for this problem..

def A(m,n):
    if m == 0:
        return n + 1
    elif m > 0 and n == 0:
        return A(m-1,1)
    else:
        return A(m-1,A(m,n-1))
print A(0,7)

$8$

A(0,7) = 7+1 = 8;

Maruf Billah - 7 years, 3 months ago

very nice

Mohammed Rajab - 7 years, 3 months ago

its a quit simple recursive function

Md Badiuzzaman - 7 years, 3 months ago

7 + 1 = 8

Patrick Feltes - 7 years, 2 months ago

San Malu
Mar 8, 2014

m==0 is true this implies A(0,7) should return n+1 ie 7+1 = 8

Venkappa Bhajantri
Mar 7, 2014

m=0 , value of A(0,7)=n+1; so 7+1=8,,

i don't understad how to get that aswer explain it in an easy way

Gilbert Francisco - 7 years, 3 months ago

in the question if m=0, A(m,n)=n+1 , so its A(0,7) n=7 , A(0,7)=7+1=8

venkappa Bhajantri - 7 years, 3 months ago

Jeremy Shuler
Mar 2, 2014

Since A(0,n) = A(m,n) when m=0, and n=7, and A(m,n) when m=0 is n+1, and since n=7, the answer is 8.

Prasun Biswas
Feb 23, 2014

Turbo C++ code for this problem and it also works for part 2 of this problem if you change the parameters of the function A to (3,6) in the line tot=A(0,7).

#include<iostream.h>
#include<conio.h>
long A(int,int);
void main()
    {
    int tot;
    clrscr();
    tot=A(0,7);
    cout<<endl<<tot;
    getch();
    }
long A(int m, int n)
    {
    long ret=0;
    if(m==0)
        {
        ret=n+1;
        return ret;
        }
    if(m>0 && n==0)
        {
        ret=A(m-1,1);
        return ret;
        }
    if(m>0 && n>0)
        {
        ret=A(m-1,A(m,n-1));
        return ret;
        }
    }

NICELY SOLVED USING C++

YASH KASAT - 7 years, 3 months ago

kashif ali - 7 years, 3 months ago

by C++ easy solveable

kashif ali - 7 years, 3 months ago

Ashish Maurya
Feb 23, 2014

java solution

public class Check{

public  static int ACC(int m, int n) {
    int ans=0;
    if(m==0){
        ans=n+1;
    }
    else if(n==0 && m>0){
        ans =  ACC(m-1,1);
    }
    else if(m>0 && n>0){
        ans = ACC(m-1, ACC(m,n-1));
    }   
    return ans; 
}
public static void main(String[] args){ 
  System.out.print(Check.ACC(3, 6));
}

}

509

Sonu Sunindra - 7 years, 3 months ago

Check.ACC(3, 6) ??? I'm new to Java ,,, I got alot of learning to do ,,

A Former Brilliant Member - 7 years, 3 months ago

Check is a class which contains method(Function) ACC if method is qualified by "static" you can call it by using a dot after class name followed by method name and input arguments

<className> . <Methodname>( input arguments) so to call the ACC method of check class Check . ACC(3,6) :)

Muhammad Irshad - 7 years, 2 months ago

It's the calling of a method within itself that I do not get ,,,, but I get it now ,,,

A Former Brilliant Member - 7 years, 2 months ago

Lokesh Sharma
Feb 14, 2014

Python Solution:

def A(m, n):
    if m == 0:
        return n+1
    elif m > 0 and n == 0:
        return A(m-1, 1)
    else:
        return A(m-1, A(m, n-1))

>>> 8

(waiting for Part 2 and 3...)

Also, because $m = 0$ , you can just use the first case of the function to get $7 + 1 = \boxed {8}$

Arman Siddique - 7 years, 3 months ago

I still don't get part 2 and 3 please can anyone explain this in a easy way

Riya chauahan - 7 years, 3 months ago

Sudhanshu Kumar
Mar 21, 2014

given A(0,7) where m=0 and n=7 A/C to condition if m=0; then A(m,n)=n+1 i.e A(m,n)=7+1=8

Pradeep Kumar
Mar 21, 2014

as in problem we have to find the value of(0,7) according to acekman function m=0 n=7 so value will be n+1=8

Amine Abisourour
Mar 15, 2014

JavaScript Solution

Minified function (with Google Closure Compiler) # function A(a, b) { return 0 === a ? b + 1 : 0 < a && 0 === b ? A(a - 1, 1) : A(a - 1, A(a, b - 1)); };

Normal function # function A(m, n) { if (m === 0) return n + 1; else if (m > 0 && n === 0) return A(m - 1, 1); else return A(m - 1, A(m, n - 1)); };

Saddam Ranjhani
Mar 13, 2014

A(m,n) = A(0,7) Beause and it says when m=0, then n+1 so 8 is answer

Rukunujjaman Miaji
Mar 12, 2014

int recu(int a,int b) if(a==0) return b+1; else if(a>0&&b==0) return recu(a-1,1); else return recur(a-1,recur(a,b-1));

Resita Wahyuni
Feb 28, 2014

because m = 0, then A(m,n) = n + 1 = 7 + 1 =8

Anand Dc
Feb 27, 2014

A(m,n)=A(0,7) m-0,then n+1, 7+1=8

Shariful Islam
Feb 27, 2014

A(0,7) = 7+1 = 8;

Maruf Billah
Feb 26, 2014

A(0,7) = 7+1 = 8;

Sathish P
Feb 23, 2014

A(0,0) =1 A(0,1)=2 . . A(0,7)=8

In general, A(0,n) = n+1

Maria Alappattu
Feb 21, 2014

From the function given, if m=0,then solution is n+1

Avijeet Kartikay
Feb 21, 2014

As it was given, if m=0, then A(m,n)=n+1, thus A(0,7)=7+1=8 =)

Maheen Ahmed
Feb 18, 2014

m=0 so we will use n+1 and that is equal to 7+1=8

Sruthi Gpillai
Feb 16, 2014

8 because a(m,n)= n+1 since m=0 and here n =7 the ans is n+1=7+1=8

Amit Rawat
Feb 15, 2014

in A(0,7) the value of m is 0 if we compare it with A(m,n). and the value of n is 7 so according to the ackermann function if m=0 then A(m,n)=n+1 which leads to A(0,7)=8 hence 8 is the answer.

Balaji Raja - 7 years, 3 months ago

Agnes Fung
Feb 14, 2014

$A(m,n) = A(0,7)$

$m=0$

$A(m,n) = n + 1$

Sri Bathalapalli - 7 years, 3 months ago

Extremely Deep Recursion - Part 1

The answer is 8.

23 solutions

java solution

public class Check{

JavaScript Solution

0 pending reports