# Recurrence question

Page 1 of 1

## 3 Replies - 543 Views - Last Post: 23 January 2018 - 01:35 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'https://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=408898&amp;s=a194e2aabc8f8e1bcbc2dabe5e35081e&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 AstroBuzz

Reputation: 0
• Posts: 2
• Joined: 23-January 18

# Recurrence question

Posted 23 January 2018 - 01:03 PM

Hi.
My method should pass n as argument and print/return all combinations of 0s and 1's but 1's should not stand next to each other.
eg.f(3) should return/print 000,001,100,010,101.
I would like to use recurrence. Is there anyone that knows how to do this?

Is This A Good Question/Topic? 0

## Replies To: Recurrence question

### #2 modi123_1

• Suitor #2

Reputation: 15115
• Posts: 60,492
• Joined: 12-June 08

## Re: Recurrence question

Posted 23 January 2018 - 01:08 PM

What have you tried, thought about, or considered?

### #3 AstroBuzz

Reputation: 0
• Posts: 2
• Joined: 23-January 18

## Re: Recurrence question

Posted 23 January 2018 - 01:15 PM

modi123_1, on 23 January 2018 - 01:08 PM, said:

What have you tried, thought about, or considered?

I thought about something like this:
```public static void zeros_ones(int n)
{
ArrayList<String> l = new ArrayList<String>();

for (int i = 0; i < n; i++)
{
}

for (int i = 0; i < n; i++)
{
l.set(i, "1");
if (i>0)
{
l.set(i-1, "0");

}
// here is the part where I would use recurrence.
ArrayList<String> l2 = new ArrayList<String>(l);

for (int j = i; j < n; ++j)
{
if (j>0 && l2.get(j-1).equals("1"))
{
continue;
}else{
l2.set(j, "1");
}

System.out.println(String.join("", l2));

}

}
}

```

I thought about concatenation of substring and execution of the method itself. eg return substring(0,i) + zeros_ones(n-1) but I'm not exactly sure what conditions should I use. Got some hint?

### #4 modi123_1

• Suitor #2

Reputation: 15115
• Posts: 60,492
• Joined: 12-June 08

## Re: Recurrence question

Posted 23 January 2018 - 01:35 PM

That's not pretty recursive. Perhaps starting with the larger problem - creating a series of strings that are permutations of 1's and 0's. (worry about the side by side bit later)

I would think the function would need an input string, the level, and the combined string.
First step would be to the check if this is level 0.. if it is exist the function since you don't want to go negative. Typically this is where I would append the 'combined string' for my checking)
Then start the work.. so decrement the level, and call the same function this time with the input string with addition to a 0.

Calling the same function is the recursion part!

When the function is returned because of hitting the level of 0 I want to it to call itself again but this time with the input string combined with '1'.

This way I should cover all the bases, right?

See if you can get it to generate all the permutations for 1 and 0.