title: Filter an immutable list recursively
body: <p>Let's say I have an array of integers, and I need to return an array of all the numbers that are divisible by 3 in order.</p>
  
  <p>I'm given the interface:</p>
  
  <pre><code>List&lt;int&gt; ListElementsDivisibleBy3Recursive(List&lt;int&gt; input)
  </code></pre>
  
  <p>So it must take a list and return a list, and filter it recursively. I've tried popping elements out of the beginning of the list until I hit a number that matches the required condition, and that's where I get stuck. I don't know how to step to the next element and keep the element that matches the condition. This is what I have so far:</p>
  
  <pre><code>static List&lt;int&gt; ListElementsDivisibleBy3Recursive(List&lt;int&gt; input)
          {
              if (input.Count == 0)
                  return input;
              else if (input.ElementAt(0) % 3 == 0)
              {
                  return ListElementsDivisibleBy3Recursive(input); &lt;--I have no idea what to do here
              }
              else
              {
                  input.RemoveAt(0);
                  return ListElementsDivisibleBy3Recursive(input);
              }
          }
  </code></pre>
  
  <p>It would be much easier if I was allowed to pass a pointer to the position in the list I'm at, but all I have is the input list and the return list to work with. How do I delete elements in the list while keeping the ones that match the conditional? Or am I going about this all the wrong way? Not sure how I should be going about this logically. I also realize that my base condition is wrong too.</p>