Recursion puzzles with solutions

1. Print out every letter in a string, one on each line, using recursion.

     P1.java 

  1  public class P1 {
  2      public static void main(String[] args) {
  3          printOut("Polar bear");
  4      }
  5  
  6      static void printOut(String x) {
  7          if (x.length() > 0) {
  8              System.out.println(x.charAt(0));
  9              printOut(x.substring(1, x.length()));
 10          }
 11          else {
 12              // Do nothing
 13          }
 14      }
 15  }

P
o
l
a
r
 
b
e
a
r

2. Calculate 1 + 2 + ... + N using recursion.

     P2.java 

  1  public class P2 {
  2      public static void main(String[] args) {
  3          System.out.println(foo(5));
  4      }
  5  
  6      static int foo(int n) {
  7          if (n > 0) {
  8              return n + foo(n-1);
  9          }
 10          else {
 11              return 0;
 12          }
 13      }
 14  }

15

3. Calculate 1 * 2 * ... * N using recursion

     P3.java 

  1  public class P3 {
  2      public static void main(String[] args) {
  3          System.out.println(foo(5));
  4      }
  5  
  6      static int foo(int n) {
  7          if (n > 1) {
  8              return n * foo(n-1);
  9          }
 10          else {
 11              return 1;
 12          }
 13      }
 14  }

120

4. Calculate 1/1² + 1/2² + ... + 1/N² (≈ π²/6) using recursion.

     P4.java 

  1  public class P4 {
  2      public static void main(String[] args) {
  3          System.out.println(foo(10));
  4      }
  5  
  6      static double foo(int n) {
  7          if (n > 0) {
  8              return 1.0/(n*n) + foo(n-1);
  9          }
 10          else {
 11              return 0;
 12          }
 13      }
 14  }

1.5497677311665408

5. Calculate 1 / 2 / ... / N using recursion.

     P5.java 

  1  public class P5 {
  2      public static void main(String[] args) {
  3          System.out.println(foo(5));
  4      }
  5  
  6      static double foo(int n) {
  7          if (n > 0) {
  8              return (1.0 / n) * foo(n-1);
  9          }
 10          else {
 11              return 1.0;
 12          }
 13      }
 14  }

0.008333333333333333

6. Calculate 1/1! + 1/2! + ... + 1/N! using recursion.

     P6.java 

  1  public class P6 {
  2      public static void main(String[] args) {
  3          System.out.println(foo(8));
  4      }
  5  
  6      static double foo(int n) {
  7          if (n > 0) {
  8              return 1.0 / factorial(n) + foo(n-1);
  9          }
 10          else {
 11              return 0;
 12          }
 13      }
 14  
 15      static double factorial(int n) {
 16          if (n > 0) {
 17              return n * factorial(n-1);
 18          }
 19          else {
 20              return 1;
 21          }
 22      }
 23  }

1.71827876984127

7. Make a string of N 'x's using recursion.

     P7.java 

  1  public class P7 {
  2      public static void main(String[] args) {
  3          System.out.println(foo(6));
  4      }
  5  
  6      static String foo(int n) {
  7          if (n > 0) {
  8              return "x" + foo(n-1);
  9          }
 10          else {
 11              return "";
 12          }
 13      }
 14  }

xxxxxx

8. Make a string of N 'a's followed by N 'b's using recursion.

     P8.java 

  1  public class P8 {
  2      public static void main(String[] args) {
  3          System.out.println(foo(7));
  4      }
  5  
  6      static String foo(int n) {
  7          if (n > 0) {
  8              return "a" + foo(n-1) + "b";
  9          }
 10          else {
 11              return "";
 12          }
 13      }
 14  }

aaaaaaabbbbbbb

9. Perform an n-place rotation of a string using recursion.

   That is, "abcdef" rotated | 0 is "abcdef" | 1 is "bcdefa" | 2 is "cdefab" | 3 is "defabc" | etc

     P9.java 

  1  public class P9 {
  2      public static void main(String[] args) {
  3          System.out.println(rotate("abcdef", 2));
  4      }
  5  
  6      static String rotate(String x, int n) {
  7          if (n > 0) {
  8              String y = rotate(x, n-1);
  9              return y.substring(1, y.length()) + y.charAt(0);
 10          }
 11          else {
 12              return x;
 13          }
 14      }
 15  }

cdefab

10. Interleave (like riffle-shuffling a deck) two strings, using recursion:

    interleave("ABCD", "abcd") = "AaBbCcDd"
    

The two strings will be the same length.

     P10.java 

  1  public class P10 {
  2      public static void main(String[] args) {
  3          System.out.println(interleave("Ade jn", "nrwTag"));
  4      }
  5  
  6      static String interleave(String x, String y) {
  7          if (x.length() > 0) {
  8              // Get just the first character
  9              String xFirst = x.substring(0, 1);
 10              String yFirst = y.substring(0, 1);
 11              return xFirst + yFirst + interleave(x.substring(1, x.length()), y.substring(1, y.length()));
 12          }
 13          else {
 14              return "";
 15          }
 16      }
 17  }

Andrew Tjang

11. Interleave two strings, like the last one, except the two strings might not be the same length:

    interleave("aaaaa", "bb") = "ababaaa"
    

     P11.java 

  1  public class P11 {
  2      public static void main(String[] args) {
  3          System.out.println(interleave("aaaa", "bb"));
  4      }
  5  
  6      static String interleave(String x, String y) {
  7          if (x.length() > 0 && y.length() > 0) {
  8              // Get just the first character
  9              String xFirst = x.substring(0, 1);
 10              String yFirst = y.substring(0, 1);
 11              return xFirst + yFirst + interleave(x.substring(1, x.length()), y.substring(1, y.length()));
 12          }
 13          else if (x.length() == 0) {
 14              return y;
 15          }
 16          else if (y.length() == 0) {
 17              return x;
 18          }
 19          else {
 20              // Not possible
 21              return "";
 22          }
 23      }
 24  }

ababaa

12. Find sin(sin(sin(...sin(x)))) (N times) using recursion.

     P12.java 

  1  public class P12 {
  2      public static void main(String[] args) {
  3          System.out.println(foo(2.4, 10));
  4      }
  5  
  6      static double foo(double x, int n) {
  7          if (n > 0) {
  8              return Math.sin(foo(x, n-1));
  9          }
 10          else {
 11              return x;
 12          }
 13      }
 14  }

0.43117735749156655

13. Find out how many times you have to divide a number by 2 until it becomes 0, using recursion.

    So for example:

    4 / 2 / 2 / 2 = 0   3 times
    20 / 2 / 2 / 2 / 2 / 2 = 0   5 times
    

     P13.java 

  1  public class P13 {
  2      public static void main(String[] args) {
  3          System.out.println(foo(20));
  4      }
  5  
  6      static int foo(int n) {
  7          if (n > 0) {
  8              return 1 + foo(n/2);
  9          }
 10          else {
 11              return 0;
 12          }
 13      }
 14  }

5

14. Find how many steps it takes the 3n+1 sequence to reach 1, using recursion:

    n[k+1] = 3*n + 1   if n is odd
             n/2       if n is even
    

     P14.java 

  1  public class P14 {
  2      public static void main(String[] args) {
  3          System.out.println(howManySteps(29));
  4      }
  5  
  6      static int howManySteps(int n) {
  7          if (n == 1) {
  8              return 0;
  9          }
 10  
 11          int nextN;
 12          if (n % 2 == 1) {
 13              nextN = 3*n + 1;
 14          }
 15          else {
 16              nextN = n / 2;
 17          }
 18  
 19          return 1 + howManySteps(nextN);
 20      }
 21  }

18

15. Strip out all of the letter 'a' in a string, using recursion.

     P15.java 

  1  public class P15 {
  2      public static void main(String[] args) {
  3          System.out.println(foo("avada kedavra"));
  4      }
  5  
  6      static String foo(String x) {
  7          if (x.length() > 0) {
  8              if (x.charAt(0) == 'a') {
  9                  return foo(x.substring(1, x.length()));
 10              }
 11              else {
 12                  return x.charAt(0) + foo(x.substring(1, x.length()));
 13              }
 14          }
 15          else {
 16              return "";
 17          }
 18      }
 19  }

vd kedvr

Code from Recitaiton 10

1. Cause tha stack to overflow.

        Stack.java 
   
     1  
     2  public class Stack {
     3   public static void main(String[] args) {
     4    foo();
     5   }
     6   
     7   static void foo() {
     8          foo();
     9   }
    10  }
    11  
   
   

2. Count how deep the stack can grow, before overflowing.

        Depth.java 
   
     1  
     2  public class Depth {
     3   public static void main(String[] args) {
     4    foo(0);
     5   }
     6   
     7   static void foo(int counter) {
     8    System.out.println(counter);
     9    foo(counter + 1);
    10   }
    11  }
    12  
   
   

3. Dragon curve http://en.wikipedia.org/wiki/Dragon_curve

   The dragon curve is built by moving and turning according to some rules:

   • To draw an "X" of size N:

     1. Draw an "X" of size N-1
     2. Turn right
     3. Draw a "Y" of size N-1
     4. Go forward
     5. Turn right

   • To draw a "Y" of size N:

     1. Turn left
     2. Go forward
     3. Draw an "X" of size N-1
     4. Turn left
     5. Draw a "Y" of size N-1

   You can use the Turtle class to draw:

   • Turtle.draw(number of pixels)
   • Turtle.turn(number of degrees)

   Draw a dragon curve.

        Fractal.java 
   
     1  
     2  public class Fractal {
     3   public static void main(String[] args) {
     4    x(10);
     5   }
     6   
     7   static void x(int n) {
     8    if (n == 0) {
     9    }
    10    else {
    11     x(n - 1);
    12     Turtle.turn(90);
    13     y(n - 1);
    14     Turtle.draw(10);
    15     Turtle.turn(90);
    16    }
    17   }
    18   
    19   static void y(int n) {
    20    if (n==0) { 
    21    }
    22    else {
    23     Turtle.turn(-90);
    24     Turtle.draw(10);
    25     x(n - 1);
    26     Turtle.turn(-90);
    27     y(n - 1);
    28    }
    29   }
    30  }
    31  
    32