Problem of the Day

Problem:

A certain species of tree always produces branches in pairs, and can be modeled as follows: if it has n = 0 forks, it only has one "segment" of wood, its trunk. If it has n = 1 fork level it has three segments of wood: the trunk and two branches. And if it has n = 2 fork levels it has seven segments of wood, as shown.

Identify which recursive function will return the correct number of segments of wood, given a fork level n.

1. 
   

   public static int recurse(int n)
   {
       if (n == 0)
           return 1;
       else
           return 2 + recurse(n - 1);
   }

2. 
   

   public static int recurse(int n)
   {
       if (n == 0)
           return 1;
       else
           return 1 + 2 * recurse(n - 1);
   }

3. 
   

   public static int recurse(int n)
   {
       if (n <= 1)
           return 1;
       else
           return 1 + 2 * recurse(n - 1);
   }

4. 
   

   public static int recurse(int n)
   {
       if (n == 0)
           return 0;
       else
           return 1 + 2 * recurse(n - 1);
   }

Show solution: