Ackermann Table Geneation

Question

I'm working on learning more about Ackermann's function, recursion time, and functionology in general, however, my code won't compile. I have a feeling it's something to do with the arrays in acktgen(), but I'm not 100% certain.

#include <stdlib.h>
#include <iostream>
using namespace std;

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

int acktgen(const int s, const int t){
    int acktable[s+1][t+1];
    for (int i = 1 ; i= t+1; ++i){ //column labels
        acktable[0][i]= i-1 ;
    }
    for (int i = 1 ; i= s+1; ++i){  //row labels
        acktable[i][0]= i-1 ;
    } 
    for (int i = 1; i<=s+1; ++i){
        for (int j = 1; j<=t+1; ++j){
            acktable[i][j]= ack(i-1,j-1);
        }
    }
    return(acktable);
}

int main(){
    for(int i=0;i<5;i++) {
        for(int j=0;j<5;j++) {
            cout<<acktgen(4,4)[i][j]<< "\t";
        }
    }
}

I know this isn't the most efficient Ackermann algorithm, but I'm just using it as an example.

Compiler Error:

prog.cpp: In function 'int acktgen(int, int)':
prog.cpp:26:17: error: invalid conversion from 'int (*)[(t + 1)]' to 'int' [-fpermissive]
  return(acktable);
                 ^
prog.cpp:14:6: warning: address of local variable 'acktable' returned [-Wreturn-local-addr]
  int acktable[s+1][t+1];
      ^
prog.cpp: In function 'int main()':
prog.cpp:32:24: error: invalid types 'int[int]' for array subscript
    cout<<acktgen(4,4)[i][j]<< "\t";
                        ^

Answer 1

Let's go through each error and warning:

> prog.cpp: In function 'int acktgen(int, int)': prog.cpp:26:17: error:
> invalid conversion from 'int (*)[(t + 1)]' to 'int' [-fpermissive]  
> return(acktable);

You declared your acktgen function to return an int, but instead you're returning an address. I don't know what your intention is here, but if it is to return a single value from the array, then you return that value, i.e.

return acktgen[0][4];

or something like that.

---

> prog.cpp:14:6: warning: address of local variable 'acktable' returned
> [-Wreturn-local-addr]   int acktable[s+1][t+1];

You are returning the address of a local variable. Doing so is undefined behavior in C++, so don't do it. When the function returns, all local variables go away. Therefore attempting to return (and use) the address of something that isn't there isn't going to work (or it may work, but only by chance).

---

> prog.cpp: In function 'int main()': prog.cpp:32:24: error: invalid
> types 'int[int]' for array subscript
>     cout<<acktgen(4,4)[i][j]<< "\t";

This is not correct, due to acktgen returning an int, not an array or array-like object.

Basically you need to give us more information on what you expected to return in the acktgen function. Was it really supposed to be an array? Was it supposed to be just a single value?

---

Some things with your code:

1) Declaring arrays with non constant expressions is not legal in ANSI C++:

int acktable[s+1][t+1];

That line of code is not legal C++. To simulate an array, you can use std::vector<std::vector<int>>:

std::vector<std::vector<int>> acktable(s+1, std::vector<int>(t+1));

2) Your loop condition is written incorrectly:

   for (int i = 1 ; i = t+1; ++i){ //column labels

Look at the middle condition -- is that what you want, that the loop only continues if i == t+1 ? You make the same mistake in the loop afterwards.

Second, your loops access the array out-of-bounds. Arrays in C++ are 0-based, but if you look at your loop closely, you go one over the edge:

    for (int i = 1; i<=s+1; ++i){
        for (int j = 1; j<=t+1; ++j){
            acktable[i][j]= ack(i-1,j-1);
        }
    }

What happens on the last iteration? You access acktable[s+1][t+1], which is out of bounds. The highest indices for that array are s and t, since we start counting at 0.