How to recursively repeat n times the elements in an array?

user_17584242 0
Viewed 245

I'm trying to find the recursive function for this problem, to be more clear:

  • Input = [8, 4, 3, 4}
  • n = 3
  • Output = [8, 8, 8, 4, 4, 4, 3, 3, 3, 4, 4, 4]

I've solved it using iteration and loop, but since I was just introduced to recursive methods, I'm still struggling pretty hard with this problem in particular. This is my iterative solution for it.

public class repeatElement {

public static void main(String[] args) {
    int[] a = {1, 2, 3};
    int n, j, i;
    n = Integer.parseInt(JOptionPane.showInputDialog("Enter n"));
    int[] b = new int[a.length * n];

    for (i = 0; i < a.length; i++) {
         for (j = n*i; j < n*(i+1); j++) {
            if (j % n == 0) {
                b[j] = a[i];
            }
            if (j % n != 0) {
                b[j] = a[i];
            }
        }
    }
    JOptionPane.showMessageDialog(null, Arrays.toString(b));
}
recursion arrays java
2 Answers

You can simulate a for loop with recursion by having an extra index parameter. At the end of the method, recursively call the method again with index + 1. The method should return when index reaches the end of the array, just like a for loop:

private static void repeatEachElement(int times, int[] input, int[] output, int index) {
    // stopping condition
    if (index == output.length) {
        return;
    }

    // this is where it fills the array.
    output[index] = input[index / times];

    // calls itself again with index + 1
    repeatEachElement(times, input, output, index + 1);
}

Note that I'm "looping" over the output array, so that I don't need another loop to fill each index. I can just get the element that should be at that index by doing input[index / times].

To call this method, you would need to create an output array of the correct length first, and index must start at 0. You can wrap this method into a more convenient method:

private static int[] repeatEachElement(int times, int[] input) {
    int[] output = new int[input.length * times];
    repeatEachElement(times, input, output, 0);
    return output;
}

Then you can do:

int[] input = {8, 4, 3, 4};
System.out.println(Arrays.toString(repeatEachElement(3, input)));
// [8, 8, 8, 4, 4, 4, 3, 3, 3, 4, 4, 4]

At the end of the day though, there isn't much point in doing this recursively in Java, other than to learn about how recursion works. It is less readable than a loop, and will overflow the stack if the array is long enough.

user_51335850

I can offer the solution of your problem, using the algorithm Depth first search.

/*
Input = [8, 4, 3, 4],
n = 3,
Output = [8, 8, 8, 4, 4, 4, 3, 3, 3, 4, 4, 4].
*/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int maximumSize=40;
vector<int> visited(maximumSize, 0);
void showContentVector(vector<int>& input)
{
    for(int i=0; i<input.size(); ++i)
    {
        cout<<input[i]<<", ";
    }
    return;
}
void dfs(int current, int previous, vector<int>& input, int number)
{
    if(visited[current]==1)
    {
        return;
    }
    visited[current]=1;
    int inputSize=input.size();
    vector<int> numbers;
    for(int i=0; i<number; ++i)
    {
        numbers.push_back(input[current]);
    }
    for(int next=(current+1); next<inputSize; ++next)
    {
        if(next==previous)
        {
            continue;
        }
        dfs(next, current, input, number);
    }
    for(int i=0; i<numbers.size(); ++i)
    {
        input.push_back(numbers[i]);
    }
    if(current==0)
    {
        vector<int> temporary;
        for(int i=inputSize; i<input.size(); ++i)
        {
            temporary.push_back(input[i]);
        }
        reverse(temporary.begin(), temporary.end());
        input.clear();
        for(int i=0; i<temporary.size(); ++i)
        {
            input.push_back(temporary[i]);
        }
    }
    return;
}
int main()
{
    vector<int> inputVector={8, 4, 3, 4};
    cout<<"inputVector <- ";
    showContentVector(inputVector);
    cout<<endl;
    dfs(0, -1, inputVector, 3);
    cout<<"inputVector <- ";
    showContentVector(inputVector);
    cout<<endl;
    return 0;
}

Here is the result:

inputVector <- 8, 4, 3, 4, 
inputVector <- 8, 8, 8, 4, 4, 4, 3, 3, 3, 4, 4, 4,
user_52022600
Related