Extremely Deep Recursion - Ackermann

Computer Science Level 2

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(3,6)?$

The answer is 509.

36 solutions

Thaddeus Abiy
Feb 14, 2014

Solution in Python..

    def A(m, n):
        if m == 0:
            return n+1
        if n == 0:
            return A(m-1, 1)
        return A(m-1, A(m, n-1))

    print A(3, 6)
    #Prints 509

I think that un this example is better to use dynamic programming. Create a memory dict: mem={} Then when you compute A(m,n) for the first time you set mem[m,n]=A(m,n) and whe you ask again for the same m and the same n you can return directly mem[m,n] The improvement in recursive calls for m=3 and n=6 is from 172233 to just 1277

Daniel Crego - 5 years ago

return A(m-1,A(m,n-1))

Thaddeus Abiy - 7 years, 3 months ago

In the solution I think an else statement is missing, was the goal to do it by hand or by building the program. def A(m, n): if m == 0: return n+1 if n == 0: return A(m-1, 1) else: return A(m-1, A(m, n-1))

Bernardo Garci - 7 years, 3 months ago

There's no need for else statement, considering that each conditional returns a value, thus breaking the execution of the thread.

João Arruda - 5 years, 5 months ago

Arman Siddique
Feb 14, 2014

Ackermann function in Python:

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

Calling $a(3, 6)$ gives $\boxed {509}$ .

sorry I can't understand< how did u get the answer?

Reem Yacout - 7 years, 3 months ago

The function $a$ implements the Ackermann function (the function in the problem). By calling $a(3, 6)$ , we get the value that we're looking for (the Ackermann function with $(m=3, n=6)$ ).

Arman Siddique - 7 years, 3 months ago

exactly

Gabriel Scheller - 7 years, 3 months ago

A(m-1,A(m,n-1))

Muhammad Khan - 7 years, 3 months ago

how aboout pascal man? uses crt; function ac(m,n:integer):integer; begin if (m=1)and(n=2) then ac:=4; if (m=2)and(n=2) then ac:=7; if (m=3)and(n=2) then ac:=29; if m=0 then ac:=n+1 else if (m>0)and(n=0) then ac:=ac(m-1,1) else if (m>0)and(n>0) then ac:=ac(m-1,ac(m,n-1)); end; begin writeln('Hello, world!'); writeln('ackermann là ',ac(3,6)); end.

Vũ Trung - 7 years, 3 months ago

Lokesh Sharma
Feb 15, 2014

Python's 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))

This is not any different to the solution by Lokesh Sharma

Ray Hamilton - 3 years, 10 months ago

Prasun Biswas
Feb 16, 2014

I used Turbo C++ and this here is my code :

#include<iostream.h>
#include<conio.h>
long A(int,int);
void main()
    {
    int tot;
    clrscr();
    tot=A(3,6);
    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;
        }
    }

Try A(4,5) instead of A(3,6) and tell me what happens .

Aakarshit Uppal - 7 years, 3 months ago

Actually, this program will give incorrect garbage values if you try A(4,5) as the Ackermann function grows rapidly and the value returned in case of A(4,5) is too big to be stored even in "long long" type variable.

Prasun Biswas - 7 years, 3 months ago

you got it ;) (i was just kidding)

Aakarshit Uppal - 7 years, 3 months ago

Abhishek Sharma - 7 years, 3 months ago

I'm using the same code as your but my code shows 42670

Gery Wahyu - 7 years, 3 months ago

It might be that the compiler of your TC++ is functioning incorrectly. It happens in my PC also sometimes. Your compiler version must be old and therefore not calculating the values properly and returning garbage values as output.

Prasun Biswas - 7 years, 3 months ago

Santanu Banerjee
Feb 19, 2014

import java.io.*;

import java.math.*;

public class ExtremelyDeepRecursionPart2

{

public static void main(String args[])

{

    long x=3L,y=6L;

    ExtremelyDeepRecursionPart2 obj=new ExtremelyDeepRecursionPart2();

    System.out.println(obj.fun(x,y));

}

long fun(long m,long n)

{

    if(m==0)

        return n+1;

    else if(n==0 && m>0)

        return fun(m-1,1);

    else if(m>0 && n>0)

        return fun(m-1,fun(m,n-1));

    return -1;

}

}

Output :: 509

Стефан Војводић
Apr 27, 2018

Here is a solution in js (you can run it in browser on the same page :D):

let ack = (m, n) => {
    if (m === 0) return n+1
if (m > 0 && n === 0) return ack(m-1, 1)
if (m > 0 && n > 0) return ack(m-1, ack(m,n-1))
}

// returns 509
ack(3,6)

Jesse Nieminen
Nov 21, 2015

def A(m, n):
    if m == 0:
        return n + 1
    if m > 0 and n == 0:
        return A(m - 1, 1)
    if m > 0 and n > 0:
        return A(m - 1, A(m, n - 1))
print(A(3, 6))

1
2
3

509

Process finished with exit code 0

Matthew Christopher
Jul 28, 2020

A solution in C#:

static void Main(string[] args)
{
    Console.Write("m = ");
    int m = int.Parse(Console.ReadLine());
    Console.Write("n = ");
    int n = int.Parse(Console.ReadLine());
    Console.WriteLine(Ackerman(m, n));
}

public static int Ackerman(int m, int n)
{
    if (m == 0)
    {
        return n + 1;
    } else if (m > 0 && n == 0)
    {
        return Ackerman(m - 1, 1);
    } else if (m > 0 && n > 0)
    {
        return Ackerman(m - 1, Ackerman(m, n - 1));
    }

    return -1;
}

1
2
3

m = 3
n = 6
509

Paras Sidhu
Jun 18, 2020

I solved it in Kotlin using Dynamic Programming.

Used num variable to store number of times recursive function is called and map is used for DP (to store the results of calculations).
In the acker function, we simply see if the value is in map then return it otherwise follow the definition of the Ackermann function, store the value in map and return the result

For the output, I got 509 as the result and 1536 as number of recursive calls (compared to 172233 calls without DP (map)).

var num = 0
val map = mutableMapOf<Pair<Long,Long>, Long>()

fun main() {
    println(acker(3,6))
    println(num)
}

fun acker(m: Long, n: Long): Long {
    num++

    if (map.containsKey(Pair(m, n)))
        return map[Pair(m, n)]!!

    val result: Long

    when {
        m == 0L -> return n + 1
        m > 0L && n == 0L -> result =  acker(m - 1, 1)
        else -> result = acker(m - 1, acker(m, n - 1))
    }

    map[Pair(m, n)] = result
    return result
}

Siva Budaraju
Apr 13, 2017

Java:

public class Ackermann {

public static void main(String[] args) { System.out.println(a(3,6)); }

public static int a(int m, int 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));

}

Vincent Miller Moral
Jun 14, 2016

I think this has similar problem in Project Euler. Most of the solutions implement recursion but there's one user who suggested an optimitization. Kudos! :)

Reajul Haque Reayz
Oct 8, 2015

include<bits/stdc++.h>

using namespace std;

int ans(int m, int n)

{

if(m==0) return n+1;

else if(n==0 and m>0) return ans(m-1,1);

else if(m>0 and n>0) return ans(m-1, ans(m, n-1));

}

int main()

{

int m,n;

cin>>m>>n;

cout<<ans(m,n)<<endl;

return 0;

}

Valerian Pratama
Jun 9, 2015

My answer in C++

Rohti Vaidya
Mar 29, 2014

Converted the recursion into a java program. Tried (4,2) and got a StackOverFlowError ;) It really grows fast. static int deepRecursion(int m,int n) { int y=0; if(m==0) return n+1; if(m>0&&n==0) y=deepRecursion(m-1, 1); if(m>0&&n>0) y=deepRecursion(m-1, deepRecursion(m, n-1)); return y; }

Amit Kumar Swami
Mar 28, 2014

Java:

    public int ackermann(int m, int n){
        if(m == 0)
            return n+1;
        if(m > 0 && n == 0)
            return ackermann(m-1,1);
        return ackermann(m-1, ackermann(m, n-1));
    }

Anil T
Mar 25, 2014

int func(int m, int n){ if(m == 0){ return n+1; } else if( m>0 && n==0){ return func(m-1,1); } else{ return func(m-1,func(m,n-1)); } }

Santosh Shaw
Mar 20, 2014

Using C++

include<iostream.h>

include<conio.h>

include<stdlib.h>

include<stdio.h>

unsigned long ak(int,int);

void main() { clrscr(); unsigned long ans=0; ans=ak(3,6); cout<<ans; getch();

} unsigned long ak(int m,int n) { unsigned long a=0; if(m==1&&n==2) a=4; if(m==2&&n==2) a=7; if(m==3&&n==2) a=29; if(m==0) a=n+1; if(m>0&&n==0) a=ak(m-1,1); if(m>0&&n>0) a=ak(m-1,ak(m,n-1));

return a;

}

Shibi Raj
Mar 13, 2014

Python code : def acker (m,n) : if(m==0) : return n+1 elif(m>0 and n==0) : return acker(m-1,1) elif(m>0 and n>0): return acker(m-1,acker(m,n-1)) print acker(3,6)

returns 509

Chết Chắc
Mar 13, 2014

C# solution:

   public static int Ackerman(int m, int n)
    {
        if (m == 0)
        {
            return n + 1;
        }
        else if (m > 0 && n == 0)
        {
            return Ackerman(m - 1, 1);
        }
        else
        {
            return Ackerman(m - 1, Ackerman(m, n - 1));
        }
    }

வினோத் மு
Mar 13, 2014

class Ackermann { private Int64 _total=0;

    public Int64 m
    { get; set; }
    public Int64 n
    { get; set; }
    public Int64 Total
    { get { return _total; } }

    public Ackermann(Int64 m, Int64 n)
    {
        this.m = m;
        this.n = n;
        this._total = 0;
        this._total = _process(m, n);
    }
    public Int64 _process(Int64 m, Int64 n)
    {
        if (m == 0)
            return n+1;
        else  if (m > 0 && n == 0)
            return _process(m - 1, 1);
        else if(m>0 && n>0)
            return _process(m-1,_process(m,n-1));
        return 0;
    }
}

Its not complete solution. Im getting overflow error if i give 3,9 for m and n

Hazem Ahmed
Mar 12, 2014

Solution in C

int Ackermann function(int m , int n){ if (m==0) return n+1 ; if(m>0) { if (n==0) return Ackermann function(m-1,1); if(n>0) return Ackermann function(m-1,Ackermann function(m , n-1)); } }

Nitesh Yadav
Mar 12, 2014

Solved it in Ruby

class Akermann

def initialize 
    @cost = Array.new(5) { Array.new(5) } 
end

def calculate(m , n)
    if m == 0 
        @cost[m][n] = n + 1; 
    elsif m > 0 and n == 0 
        if @cost[m-1][1].nil? 
            @cost[m][n] = calculate(m-1, 1)
        else 
            @cost[m][n] = @cost[m-1][1] 
        end
    elsif m > 0 and n > 0 
        if @cost[m][n-1].nil? 
            @cost[m][n-1] = calculate(m,n-1)
        end
        if @cost[m-1][@cost[m][n-1]].nil? 
            @cost[m][n] = calculate(m-1, @cost[m][n-1]) 
        else
            @cost[m][n] = @cost[m-1][@cost[m][n-1]] 
        end
    end
    return @cost[m][n]
end

end

a = Akermann.new puts "A(3,6) = " + a.calculate(3, 6).inspect

Sunny Dyal
Mar 11, 2014

Solution in Java...

###### if you see stack over flow exception don't worry you just need to increase java stack size. By default it is 400k. You can increase this by adding vm argument -Xss<<value>>k/m for example java -Xss1024k Ackermann.

  public class Ackermann
  {
    public static void main(String[] args)
    {
      Ackermann ackermann = new Ackermann();
      System.out.println(ackermann.ackermann(3l,6l));
    }
    private long ackermann(long m, long n)
    {
      if (m == 0)
        return n + 1;
      if (m > 0 && n == 0)
        return ackermann(m - 1,1);
      return ackermann(m - 1,ackermann(m,n - 1));
    }
  }

Mayank Verma
Mar 9, 2014

Solution in C++

include<iostream.h>

int A(int m, int n){

if(m==0) return n+1;

else if(m>0 && n==0) return A(m-1,1);

else if(m>0 && n>0) return A(m-1,A(m,n-1));

}

int main(){

int a=3,b=6;

cout<<A(a,b);

}

Karan Kamdar
Mar 6, 2014

my perl scrip to do this :

sub ack{
my ($m,$n)=@_;
if ($m==0){return $n+1}
elsif($m>0 and $n==0){ack($m-1,1)}
else {ack($m-1,ack($m,$n-1))}

Sumit Raj
Mar 1, 2014

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

print rec(3,6)

Vaibhav Jain
Mar 1, 2014

def func(m,n):

if (m==0):

    return (n+1)

elif(m>0 and n==0):

    return func(m-1,1)

elif(m>0 and n>0):

    b=func(m,n-1)

    return func(m-1,b)

else:

    print "Invalid Input"

    exit(0)

m=int(input("enter M"))

n=int(input("enter N"))

a = func(m,n)

print a

Syed Haider
Feb 28, 2014

%In MATLAB % Call function in Command window like ackermannFunction(3,6)

function A = ackermannFunction(m,n)
set(0,'RecursionLimit',1000000000000000000)    
if m == 0
A = n+1;
elseif (m > 0) && (n == 0)
A = ackermannFunction(m-1,1);
else
A = ackermannFunction( m-1,ackermannFunction(m,n-1) );
end
end

Nimisha Soni
Feb 25, 2014

Solution in Python The Logic

if m == 0:
    return n+1
if n == 0:
    return func(m-1, 1)
return func(m-1, func(m, n-1))

Arefin Zaman
Feb 24, 2014

Here's a recursive code in C++.

include<iostream>

using namespace std; int A(int,int);

int main() { cout<<A(3,6);

return 0;

}

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

Geoffrey L. Sandja
Feb 24, 2014

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

Addin Batupahat
Feb 23, 2014

Simple Solution in ANSI-C

include <stdio.h>

long int acker(int m,int n) { if(m==0) return n+1; else if(n==0) return acker(m-1,1); else //Berarti m != n dan n != 0 return acker(m-1,acker(m,n-1)); } int main() { printf("%ld\n",acker(3,6)); return 0; }

Ram Chandran
Feb 22, 2014

My solution in c

int auck(int m, int n) { if(m==0) return n+1;
else if (m>0&&n==0) auck(m-1,1); else if (m>0&&n>0) auck(m-1,auck(m,n-1)); }

Pramod Nandy
Feb 20, 2014

A(3,4) = A(2,A(3,6)) = 2 ^(6+3) - 3 = 509

Youssef Alba
Feb 16, 2014

public int inFibo(int m,int n) { if (m==0) { return n+1;

    }
    else if (m>0 && n==0)
    {
        return inFibo(m-1,1);
    }
    return inFibo(m-1,inFibo(m,n-1));

}

Rachit Agarwal
Feb 16, 2014

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

what is the difference between function pointers and pointer to function

ROHINI maheswari - 7 years, 3 months ago

Extremely Deep Recursion - Ackermann

The answer is 509.

36 solutions

include<bits/stdc++.h>

include<iostream.h>

include<conio.h>

include<stdlib.h>

include<stdio.h>

Solution in Java...

###### if you see stack over flow exception don't worry you just need to increase java stack size. By default it is 400k. You can increase this by adding vm argument -Xss<<value>>k/m for example java -Xss1024k Ackermann.

include<iostream.h>

include<iostream>

include <stdio.h>

0 pending reports