C#•17mo ago

Memory Referrence Issue In Recursive Algorithm

Hello, I have a problem with the algorithm in the picture. What it does is take the values from a single dimensional array and puts them into an N dimensional array (additional explanation in the picture). This algorithm is recursive, and my problem I have is with the 'indexerArr' array of integers, where when the function calls itself again, then returns to itself, the function will remember the changes that were done to the indexer array in the self call. For example, let's say that the function receives the following parameters: arr = { 1, 2, 3, 7, 8, 9 } arrToAssemble = { {3, 2, 1}, {9, 8, 7} } indexerArr = { 0, 0 } currRank = 0 The function will enter the first for loop, call itself, and in that call the second for loop will be executed. And the 'arrToAssemmble' array returned will be { {1, 2, 3}, {9, 8, 7} } and the indexer array which is NOT returned will be { 0, 3 }, then it will become { 1, 3 }, and upon calling itself again, it will arrive at the second for loop which will not run because of the index being out of range. It's like the function returning to itself a parameter which is not supposed to return. Any suggestions to solve this?

10 Replies

TalOP•17mo ago

I want to note that I currently work in C# .Net Framework console applications. I'm a high school student. This is the algorithm that's in the picture if you wish to run it:

C++
//Argugment(s) receivevd: a generic array (T[]), Array object, an int[] array, an integer.
        //Argument(s) returned: assembled array of a required rank.
        //Notes: the function "assembles" an array of N dimensions from the generic array that was received.
        //This means that both arrays have to have the same total amount of indexes.

        //The indexer array ('indexerArr') is used as the indexer for placing the values in the array that needs to be assembled,
        //this is done with the method .SetValue(), which has an overload where the value is received and then the index of the value as an array, instead of the usual way of 'arrToAssemble[x, y, z, ...] = val'. This allows to deal with arrays with any number of dimensions
        //(as long as the computer is able to handle it).
        public static Array ArrAssembler<T>(T[] arr, Array arrToAssemble, int[] indexerArr, int currRank = 0)
        {
            if (arr == null || arrToAssemble == null) return null;  //Check if either array is empty.

            if (currRank < arrToAssemble.Rank - 1)
                for (; indexerArr[currRank] < arrToAssemble.GetLength(currRank) ; indexerArr[currRank]++)   ///First for loop.
                    arrToAssemble = ArrAssembler(arr, arrToAssemble, indexerArr, currRank + 1); //Reaching the dimension where values need to be placed.

            else if (currRank == arrToAssemble.Rank - 1)
                for (; indexerArr[currRank] < arrToAssemble.GetLength(currRank) ; indexerArr[currRank]++)   ///Second for loop.oo
                    arrToAssemble.SetValue(arr[indexerArr[currRank]], indexerArr);  //Placing the corresponding values from 'arr'
                    //in the indexes of 'arrToAssemble' at the current dimension.

            return arrToAssemble;
        }
        //ArrAssembler - END

C++
//Argugment(s) receivevd: a generic array (T[]), Array object, an int[] array, an integer.
        //Argument(s) returned: assembled array of a required rank.
        //Notes: the function "assembles" an array of N dimensions from the generic array that was received.
        //This means that both arrays have to have the same total amount of indexes.

        //The indexer array ('indexerArr') is used as the indexer for placing the values in the array that needs to be assembled,
        //this is done with the method .SetValue(), which has an overload where the value is received and then the index of the value as an array, instead of the usual way of 'arrToAssemble[x, y, z, ...] = val'. This allows to deal with arrays with any number of dimensions
        //(as long as the computer is able to handle it).
        public static Array ArrAssembler<T>(T[] arr, Array arrToAssemble, int[] indexerArr, int currRank = 0)
        {
            if (arr == null || arrToAssemble == null) return null;  //Check if either array is empty.

            if (currRank < arrToAssemble.Rank - 1)
                for (; indexerArr[currRank] < arrToAssemble.GetLength(currRank) ; indexerArr[currRank]++)   ///First for loop.
                    arrToAssemble = ArrAssembler(arr, arrToAssemble, indexerArr, currRank + 1); //Reaching the dimension where values need to be placed.

            else if (currRank == arrToAssemble.Rank - 1)
                for (; indexerArr[currRank] < arrToAssemble.GetLength(currRank) ; indexerArr[currRank]++)   ///Second for loop.oo
                    arrToAssemble.SetValue(arr[indexerArr[currRank]], indexerArr);  //Placing the corresponding values from 'arr'
                    //in the indexes of 'arrToAssemble' at the current dimension.

            return arrToAssemble;
        }
        //ArrAssembler - END

Omnissiah•17mo ago

so you are speaking about cloning arrays?

TalOP•17mo ago

I tried using the .Clone() function but it didn't help

TalOP•17mo ago

here

Heiholf•17mo ago

I haven't fully understood what the function should do nor how the code works but I think the problem has something to do with mutability. All variables that aren't "simple" like ints, doubles, chars, etc. are passed by reference and keep their "state" even if you leave the scope. For example in this code:

public static void Main()
    {
        int[] ints = {1, 2 ,3};
        
        printAndEdit(ints);
        printAndEdit(ints);
    }
    
    public static void printAndEdit(int[] list)
    {
        Console.WriteLine(list[0]);
        list[0] = 5;
    }

public static void Main()
    {
        int[] ints = {1, 2 ,3};
        
        printAndEdit(ints);
        printAndEdit(ints);
    }
    
    public static void printAndEdit(int[] list)
    {
        Console.WriteLine(list[0]);
        list[0] = 5;
    }

The output is: 1 5 Because the array "remembered" the change. The cloning there does not help because you already mutate the array in the for loop with indexerArr[currRank]++

TalOP•17mo ago

Yeah that's the problem I'm having. I can show a video with debug tracking if you wish

Heiholf•17mo ago

The safest (maybe not best/optimal) way to fix this is to clone indexerArr in the beginning as clone or something like that and only mutate that Clone

TalOP•17mo ago

I'm trying to develop an algorithm to sort an array of N dimensions, as a challenge I gave myself before the for loop?

Heiholf•17mo ago

Directly after if (arr == null || arrToAssemble == null) return null; This would prevent the array changes from "leaking" into the next recursion but I'm not sure if you may want that to some extent because I do not understand the function completely. Have you tried an iterative approach yet, this may resolve the problem all together.

TalOP•17mo ago

Thank you for your help, but I don't think an iterative approach will work, since I'm dealing with an N dimensional array, meaning that the amount of dimensions isn't known ahead of time, and using the foreach statement likely won't help here since it's more useful to getting the values rather than setting them I just had an idea to declare a copy of the existing indexer array using the Array class Didn't work. * sigh * I'll continue to think I tried the .Clone() function again and tracked it, found out that the referrence issue was solved, but now I have another which is easier to tackle. Thank you very much for the help!

Gaming

Programming

Memory Referrence Issue In Recursive Algorithm