# Ackermann function

**URL:** <https://fortran-lang.discourse.group/t/ackermann-function/1239>\
**Category:** Uncategorized\
**Created:** [May 16, 2021, 1:15am UTC](https://fortran-lang.discourse.group/t/ackermann-function/1239 "2021-05-16T01:15:36Z")\
**Posts on this page:** 7\
**Page:** 1

<div class="post-metadata">

**Author:** ![Beliavsky](https://avatars.discourse-cdn.com/v4/letter/b/ba8739/32.png) [@Beliavsky](https://fortran-lang.discourse.group/u/Beliavsky)\
**Post date:** [May 16, 2021, 1:15am UTC](https://fortran-lang.discourse.group/t/ackermann-function/1239/1 "2021-05-16T01:15:36Z")

</div>

Michael Wirth [presents](https://craftofcoding.wordpress.com/2021/05/13/recursion-ackermanns-function-ii/) in the The Craft of Coding Blog a Fortran function to compute the Ackermann function. Using it in

```
module ack_mod
implicit none
private
public :: Ackermann
contains
recursive function Ackermann(m,n) result(a)
integer, intent(in) :: m,n
integer :: a
if (m==0) then
   a = n + 1
else if (n==0) then
   a = Ackermann(m-1, 1)
else
   a = Ackermann(m-1, Ackermann(m, n-1))
end if
end function ackermann
end module ack_mod

program main
use ack_mod, only: Ackermann
implicit none
integer :: m,n
write (*,"(2a4,a10)") "m","n","Ack(m,n)"
do m=0,4
   do n=0,3
      if (m < 4 .or. n < 2) write (*,"(2i4,i10)") m,n,Ackermann(m,n)
   end do
end do
end program main

```

with the default compiler options for Intel, gfortran and g95 gives, [matching Wikipedia](https://en.wikipedia.org/wiki/Ackermann_function),

```
   m n Ack(m,n)
   0 0 1
   0 1 2
   0 2 3
   0 3 4
   1 0 2
   1 1 3
   1 2 4
   1 3 5
   2 0 3
   2 1 5
   2 2 7
   2 3 9
   3 0 5
   3 1 13
   3 2 29
   3 3 61
   4 0 13

```

For g95, after giving the above output the program says

```
Exception: Stack overflow
At line 26 of file ackermann.f90 (Unit 6)
Traceback: not available, compile with -ftrace=frame or -ftrace=full

```

but the Intel and gfortran programs end silently. It’s better to get an error message when a program does not end normally. Are there options to get such a message?

Compiling with `ifort /F512000000 ackermann.f90` ifort is able to compute A(4,1) = 65533. Is there a gfortran option that enables the calculation of A(4,1)?

---

<div class="post-metadata">

**Author:** ![FortranFan](https://avatars.discourse-cdn.com/v4/letter/f/96bed5/32.png) [@FortranFan](https://fortran-lang.discourse.group/u/FortranFan)\
**Post date:** [May 16, 2021, 1:34am UTC](https://fortran-lang.discourse.group/t/ackermann-function/1239/2 "2021-05-16T01:34:29Z")

</div>

> C:\temp\>gfortran -Wall -Wl,–stack -Wl,512000000 ack.f90 -o ack.exe
> 
> C:\temp\>ack.exe  
> m n Ack(m,n)  
> 0 0 1  
> 0 1 2  
> 0 2 3  
> 0 3 4  
> 1 0 2  
> 1 1 3  
> 1 2 4  
> 1 3 5  
> 2 0 3  
> 2 1 5  
> 2 2 7  
> 2 3 9  
> 3 0 5  
> 3 1 13  
> 3 2 29  
> 3 3 61  
> 4 0 13  
> 4 1 65533
> 
> C:\temp\>

---

<div class="post-metadata">

**Author:** ![Arjen](https://avatars.discourse-cdn.com/v4/letter/a/b9bd4f/32.png) [@Arjen](https://fortran-lang.discourse.group/u/Arjen)\
**Post date:** [May 17, 2021, 6:51am UTC](https://fortran-lang.discourse.group/t/ackermann-function/1239/3 "2021-05-17T06:51:46Z")

</div>

I have tried various options for Intel Fortran that have to do with checking the stack, but none resulted in a program that actually detects this problem. Odd. I even tried putting the whole code in a subroutine to see if that mattered, but that was not the case.

(Side remark 1: you could postpone the problem - and make it faster - by using a technique known as memoization.)  
(Side remark 2: I have used this function in exercises for in-house Fortran courses 🙂)

---

<div class="post-metadata">

**Author:** ![epagone](https://yyz2.discourse-cdn.com/free1/user_avatar/fortran-lang.discourse.group/epagone/32/252_2.png) [@epagone](https://fortran-lang.discourse.group/u/epagone)\
**Post date:** [May 17, 2021, 11:11am UTC](https://fortran-lang.discourse.group/t/ackermann-function/1239/4 "2021-05-17T11:11:03Z")

</div>

> [@Beliavsky](#):
>
> Is there a gfortran option that enables the calculation of A(4,1)?

With my machine

```bash
$ free -h
              total used free shared buff/cache available
Mem: 15Gi 2.4Gi 9.4Gi 508Mi 3.6Gi 12Gi
Swap: 2.1Gi 0B 2.1Gi

```

I have no issues with all the compilers available to me and no additional flags are necessary.

```bash
$ gfortran-10 -v
Using built-in specs.
COLLECT_GCC=gfortran-10
COLLECT_LTO_WRAPPER=/usr/lib/gcc/x86_64-linux-gnu/10/lto-wrapper
OFFLOAD_TARGET_NAMES=nvptx-none:amdgcn-amdhsa:hsa
OFFLOAD_TARGET_DEFAULT=1
Target: x86_64-linux-gnu
Configured with: ../src/configure -v --with-pkgversion='Ubuntu 10.3.0-1ubuntu1~20.04~2' --with-bugurl=file:///usr/share/doc/gcc-10/README.Bugs --enable-languages=c,ada,c++,go,brig,d,fortran,objc,obj-c++,m2 --prefix=/usr --with-gcc-major-version-only --program-suffix=-10 --program-prefix=x86_64-linux-gnu- --enable-shared --enable-linker-build-id --libexecdir=/usr/lib --without-included-gettext --enable-threads=posix --libdir=/usr/lib --enable-nls --enable-bootstrap --enable-clocale=gnu --enable-libstdcxx-debug --enable-libstdcxx-time=yes --with-default-libstdcxx-abi=new --enable-gnu-unique-object --disable-vtable-verify --enable-plugin --enable-default-pie --with-system-zlib --enable-libphobos-checking=release --with-target-system-zlib=auto --enable-objc-gc=auto --enable-multiarch --disable-werror --with-arch-32=i686 --with-abi=m64 --with-multilib-list=m32,m64,mx32 --enable-multilib --with-tune=generic --enable-offload-targets=nvptx-none=/build/gcc-10-S8Osas/gcc-10-10.3.0/debian/tmp-nvptx/usr,amdgcn-amdhsa=/build/gcc-10-S8Osas/gcc-10-10.3.0/debian/tmp-gcn/usr,hsa --without-cuda-driver --enable-checking=release --build=x86_64-linux-gnu --host=x86_64-linux-gnu --target=x86_64-linux-gnu --with-build-config=bootstrap-lto-lean --enable-link-mutex
Thread model: posix
Supported LTO compression algorithms: zlib zstd
gcc version 10.3.0 (Ubuntu 10.3.0-1ubuntu1~20.04~2)
$ gfortran-10 ack.f90 
$ ./a.out
   m n Ack(m,n)
   0 0 1
   0 1 2
   0 2 3
   0 3 4
   1 0 2
   1 1 3
   1 2 4
   1 3 5
   2 0 3
   2 1 5
   2 2 7
   2 3 9
   3 0 5
   3 1 13
   3 2 29
   3 3 61
   4 0 13
   4 1 65533
$ rm a.out ack_mod.mod
$ ifort -v
ifort version 2021.2.0
$ ifort ack.f90 
$ ./a.out 
   m n Ack(m,n)
   0 0 1
   0 1 2
   0 2 3
   0 3 4
   1 0 2
   1 1 3
   1 2 4
   1 3 5
   2 0 3
   2 1 5
   2 2 7
   2 3 9
   3 0 5
   3 1 13
   3 2 29
   3 3 61
   4 0 13
   4 1 65533
$ rm a.out ack_mod.mod 
$ ifx -v
ifx version 2021.2.0 Beta
$ ifx ack.f90
$ ./a.out 
   m n Ack(m,n)
   0 0 1
   0 1 2
   0 2 3
   0 3 4
   1 0 2
   1 1 3
   1 2 4
   1 3 5
   2 0 3
   2 1 5
   2 2 7
   2 3 9
   3 0 5
   3 1 13
   3 2 29
   3 3 61
   4 0 13
   4 1 65533

```

---

<div class="post-metadata">

**Author:** ![Beliavsky](https://avatars.discourse-cdn.com/v4/letter/b/ba8739/32.png) [@Beliavsky](https://fortran-lang.discourse.group/u/Beliavsky)\
**Post date:** [May 17, 2021, 11:54am UTC](https://fortran-lang.discourse.group/t/ackermann-function/1239/5 "2021-05-17T11:54:24Z")

</div>

Gfortran computes A(4,1) under WSL on my machine. On Windows, trying the gfortran compiler options of @FortranFan gives

```
c:\fortran\test>gfortran -v
Built by Equation Solution <http://www.Equation.com>.
Using built-in specs.
COLLECT_GCC=gfortran
COLLECT_LTO_WRAPPER=c:/equation/bin/../libexec/gcc/x86_64-w64-mingw32/11.0.0/lto-wrapper.exe
Target: x86_64-w64-mingw32
Configured with: ../gcc-11-20200927-mingw/configure --host=x86_64-w64-mingw32 --build=x86_64-unknown-linux-gnu --target=x86_64-w64-mingw32 --prefix=/home/gfortran/gcc-home/binary/mingw32/native/x86_64/gcc/11-20200927 --with-sysroot=/home/gfortran/gcc-home/binary/mingw32/cross/x86_64/gcc/9-20190310 --with-gcc --with-gnu-ld --with-gnu-as --with-ld64=no --with-gmp=/home/gfortran/gcc-home/binary/mingw32/native/x86_64/gmp --with-mpfr=/home/gfortran/gcc-home/binary/mingw32/native/x86_64/mpfr --with-mpc=/home/gfortran/gcc-home/binary/mingw32/native/x86_64/mpc --with-cloog=/home/gfortran/gcc-home/binary/mingw32/native/x86_64/cloog --with-diagnostics-color=auto --enable-cloog-backend=isl --enable-targets=i686-w64-mingw32,x86_64-w64-mingw32 --enable-lto --enable-languages=c,c++,fortran --enable-threads=win32 --enable-static --enable-shared=lto-plugin --enable-plugins --enable-ld=yes --enable-libquadmath --enable-libquadmath-support --enable-libgomp --disable-checking --disable-nls --disable-tls --disable-win32-registry
Thread model: win32
Supported LTO compression algorithms: zlib
gcc version 11.0.0 20200927 (experimental) (GCC) 

c:\fortran\test>gfortran -Wl,–stack -Wl,512000000 ackermann.f90
c:/equation/bin/../lib/gcc/x86_64-w64-mingw32/11.0.0/../../../../x86_64-w64-mingw32/bin/ld.exe: cannot find stack: Invalid argument
c:/equation/bin/../lib/gcc/x86_64-w64-mingw32/11.0.0/../../../../x86_64-w64-mingw32/bin/ld.exe: cannot find 512000000: No such file or directory
collect2.exe: error: ld returned 1 exit status
```

---

<div class="post-metadata">

**Author:** ![FortranFan](https://avatars.discourse-cdn.com/v4/letter/f/96bed5/32.png) [@FortranFan](https://fortran-lang.discourse.group/u/FortranFan)\
**Post date:** [May 17, 2021, 1:21pm UTC](https://fortran-lang.discourse.group/t/ackermann-function/1239/6 "2021-05-17T13:21:18Z")

</div>

> [@Beliavsky](#):
>
> `gfortran -Wl,–stack -Wl,512000000 ackermann.f90`

You seem to have applied a single hyphen before the 'stack` option. 2 hyphens are needed.

---

<div class="post-metadata">

**Author:** ![FortranFan](https://avatars.discourse-cdn.com/v4/letter/f/96bed5/32.png) [@FortranFan](https://fortran-lang.discourse.group/u/FortranFan)\
**Post date:** [May 17, 2021, 2:12pm UTC](https://fortran-lang.discourse.group/t/ackermann-function/1239/7 "2021-05-17T14:12:00Z")

</div>

> [@epagone](#):
>
> … I have no issues with all the compilers available to me and no additional flags are necessary. …

This is a Windows OS issue that OP is running into where the default stack size is rather low.