0

I am trying to learn recursion, which is a slippery concept for me. I've worked through a number of toy exercises using recursion to manipulate primitive data types and strings. But now I'm pivoting to using recursion and arrays, and here I'm stumped. I'm hoping someone can help me with perhaps the first initial step(s) in thinking about this problem.

Here's the challenge: Use recursion to set all the elements in a 1D int[] array to all 0's. No looping allowed. Conceptually, I think the solution would be:

method clearArray(int[] array)
    Check for base case:  Is array of size 1?
    IF YES:  return array
    IF NO:
       (-) Create array2, size one less than original array
       (-) Set first element of array2 to "0"
       (-) Then recursively call clearArray(array2)

On paper, this looks great. Here's the actual implementation:

public class RecursiveEx{
    public static void main(String[] args){
        int[] arr = { 1, 2, 3, 4, 5, 6, 7, 8 };
        printArray(clear(arr));
    }

    public static int[] clearArray(int[] arr){
        if(arr.length==1){
            return arr;
        }
        else{
            int[] arr2 = new int[arr.length-1];
            arr2[0]=0;
            return clearArray(arr2);
        }
    }

This returns an array of size 1, set to "0". No good. The problem is that while the code recursively chops the array down to one element, it does not build the original array back up to its original size; I don't know how to append the subarrays.

With a String this would be easy. But the String object allows for easy-to-use concatenation and substring methods. I can't figure out what the array equivalent would be.

FULL DISCLOSURE: I am taking a Java 101 course at Rutgers University, and yes, this is the first of several programming exercises they give us using recursion and arrays. Its not for credit. I'm hoping that if someone can help me get started with this initial exercise, I can see where I'm going wrong and then knock out the others.

Does anyone have some advice or recommendations? Anything would be appreciated.

Many thanks! -RAO

Improve this question
6
  • 1
    Instead of passing a chopped down array, consider passing the full array, and the index that you need to start from. Commented Apr 29, 2016 at 20:32
  • All elements of arr2 are zero already; setting arr2[0] = 0; is redundant. Commented Apr 29, 2016 at 20:35
  • Does Arrays.fill(arr, 0) count as using a loop? Commented Apr 29, 2016 at 20:37
  • 2
    return new int[arr.length] would work, but it isn't really a recursive solution :) Commented Apr 29, 2016 at 20:37
  • "On paper, this looks great" How does it look great to clear a copy of the array, when the task is to clear the original array? Commented Apr 29, 2016 at 20:44

3 Answers 3

Reset to default
1

The best approach is keeping the array as a parameter, so you always have its reference, and also the current index to keep track of the last cleared element.

I havent tested the method but it'd go like this:

void clearArray(int[] arr, int index) {
   if (index >= 0) {
       arr[index] = 0;
       clearArray(arr, index - 1);
   }
}

And you make the call clearArray(arr, arr.length - 1);

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

Please don't do other people's homework for them. See here for a guideline on answering homework questions.
He said he is struggling with the concept of recursion. An actual example usually helps. It's nothing big and it took me 5 second.s
1

To do this, I would recommend that you recursively call a helper function with an index value (incremented each time), and the array being targeted. The base case would be that your index equals the length of the array - make no further changes, and return.

The code may look something like:

import java.util.Arrays;

public class RecursiveEx {

    public static void main(String[] args) {
        int[] arr = { 1, 2, 3, 4, 5, 6, 7, 8 };
        clearHelper(0, arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void clearHelper(int index, int[] arr) {
        if (arr.length == index) {
            return;
        }
        arr[index] = 0;
        clearHelper(index + 1, arr);
    }

}

Another cheeky way without using loops: arr = Arrays.stream(arr).map(i -> 0).toArray();

Improve this answer

1 Comment

Please don't do other people's homework for them. See here for a guideline on answering homework questions.
1

Generally, re-work your thinking like so for recursion

  1. What is your input? And what are the steps needed to take to "reduce" that input into smaller pieces? What operation is needed to be done at each "step"?
  2. What is the smallest possible input that you could receive? Make that your base case (when to stop recursion).
  3. Given some input, work towards your base case from some current state and possibly using results received from a recursive call.

That being said, your input is an array, and arrays have a length property and you can index them. If you keep a reference to the entire array, and start your index at either end, then you can effectively recurse towards the other end by incrementing/decrementing the index, and setting the array at that position to zero.

In psuedocode (going backwards in the array)

func clearArray(A[], n):
    if n < 0:
        return
    A[n] = 0
    clearArray(A[], n - 1)

arr = A[]
clearArray(arr, arr.length)
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.