Codingbat recursion 1 solutions

// Given n of 1 or more, return the factorial of n, which is n * (n-1) * (n-2) ... 1. Compute the result recursively (without loops).publicint factorial(int n){if(n ==1)return1;return n*factorial(n-1); }// We have a number of bunnies and each bunny has two big floppy ears. We want to compute the total number of ears across all the bunnies recursively (without loops or multiplication).publicint bunnyEars(int bunnies){if(bunnies ==0)return0;return2+bunnyEars(bunnies-1);}// The fibonacci sequence is a famous bit of mathematics, and it happens to have a recursive definition. The first two values in the sequence are 0 and 1 (essentially 2 base cases). Each subsequent value is the sum of the previous two values, so the whole sequence is: 0, 1, 1, 2, 3, 5, 8, 13, 21 and so on. Define a recursive fibonacci(n) method that returns the nth fibonacci number, with n=0 representing the start of the sequence.publicint fibonacci(int n){if(n <2)return n;return fibonacci(n-2)+fibonacci(n-1);}// We have bunnies standing in a line, numbered 1, 2, ... The odd bunnies (1, 3, ..) have the normal 2 ears. The even bunnies (2, 4, ..) we'll say have 3 ears, because they each have a raised foot. Recursively return the number of "ears" in the bunny line 1, 2, ... n (without loops or multiplication).publicint bunnyEars2(int bunnies){if(bunnies ==0)return0;if(bunnies %2==1)return2+ bunnyEars2(bunnies-1);return3+ bunnyEars2(bunnies-1);}// We have triangle made of blocks. The topmost row has 1 block, the next row down has 2 blocks, the next row has 3 blocks, and so on. Compute recursively (no loops or multiplication) the total number of blocks in such a triangle with the given number of rows.publicint triangle(int rows){if(rows <2)return rows;return rows + triangle(rows-1);}// Given a non-negative int n, return the sum of its digits recursively (no loops). Note that mod (%) by 10 yields the rightmost digit (126 % 10 is 6), while divide (/) by 10 removes the rightmost digit (126 / 10 is 12).publicint sumDigits(int n){if(n <10)return n;return sumDigits(n/10) + n%10;}// Given a non-negative int n, return the count of the occurrences of 7 as a digit, so for example 717 yields 2. (no loops). Note that mod (%) by 10 yields the rightmost digit (126 % 10 is 6), while divide (/) by 10 removes the rightmost digit (126 / 10 is 12).publicint count7(int n){if(n ==0)return0;if(n %10==7)return1+count7(n/10);return count7(n/10);}// Given a non-negative int n, compute recursively (no loops) the count of the occurrences of 8 as a digit, except that an 8 with another 8 immediately to its left counts double, so 8818 yields 4. Note that mod (%) by 10 yields the rightmost digit (126 % 10 is 6), while divide (/) by 10 removes the rightmost digit (126 / 10 is 12).publicint count8(int n){if(n ==0)return0;if(n %10==8) {if(n /10%10==8)return2+count8(n/10);return1+count8(n/10); }return count8(n/10);}// Given base and n that are both 1 or more, compute recursively (no loops) the value of base to the n power, so powerN(3, 2) is 9 (3 squared).publicint powerN(int base, int n){if(n ==1)return base;return base*powerN(base, n -1);}// Given a string, compute recursively (no loops) the number of lowercase 'x' chars in the string.publicint countX(String str){if(str.length() ==0)return0;if(str.charAt(0) =='x')return1+ countX(str.substring(1));return countX(str.substring(1));}// Given a string, compute recursively (no loops) the number of times lowercase "hi" appears in the string. publicint countHi(String str){if(str.length() <2)return0;if(str.charAt(0) =='h'&& str.charAt(1) =='i')return1+ countHi(str.substring(2));return countHi(str.substring(1)); }// Given a string, compute recursively (no loops) a new string where all the lowercase 'x' chars have been changed to 'y' chars.publicString changeXY(String str){char ch;if(str.length() ==0)return str; ch = str.charAt(0);if(ch =='x')return'y'+ changeXY(str.substring(1));return ch + changeXY(str.substring(1));}// Given a string, compute recursively (no loops) a new string where all appearances of "pi" have been replaced by "3.14".publicString changePi(String str){String left;if(str.length() <2)return str;if(str.substring(0, 2).equals("pi"))return"3.14"+ changePi(str.substring(2));return str.charAt(0) + changePi(str.substring(1));}// Given a string, compute recursively a new string where all the 'x' chars have been removed.publicString noX(String str){char ch;if(str.length() ==0)return str; ch = str.charAt(0);if(ch =='x')return noX(str.substring(1));return ch + noX(str.substring(1));}// Given an array of ints, compute recursively if the array contains a 6. We'll use the convention of considering only the part of the array that begins at the given index. In this way, a recursive call can pass index+1 to move down the array. The initial call will pass in index as 0. publicboolean array6(int[] nums, int index){if(index == nums.length)returnfalse;if(nums[index] ==6)returntrue;return array6(nums, index +1);}// Given an array of ints, compute recursively the number of times that the value 11 appears in the array. We'll use the convention of considering only the part of the array that begins at the given index. In this way, a recursive call can pass index+1 to move down the array. The initial call will pass in index as 0.publicint array11(int[] nums, int index){if(index == nums.length)return0;if(nums[index] ==11)return1+ array11(nums, index +1);return array11(nums, index +1);}// Given an array of ints, compute recursively if the array contains somewhere a value followed in the array by that value times 10. We'll use the convention of considering only the part of the array that begins at the given index. In this way, a recursive call can pass index+1 to move down the array. The initial call will pass in index as 0.publicboolean array220(int[] nums, int index){if(index >= nums.length -1)returnfalse;if(nums[index] *10== nums[index+1])returntrue;return array220(nums, index +1);}// Given a string, compute recursively a new string where all the adjacent chars are now separated by a "*".publicString allStar(String str){if(str.length() <2)return str;return str.charAt(0) +"*"+ allStar(str.substring(1));}// Given a string, compute recursively a new string where identical chars that are adjacent in the original string are separated from each other by a "*".publicString pairStar(String str){if(str.length() <2)return str;if(str.charAt(0) == str.charAt(1))return str.charAt(0) +"*"+ pairStar(str.substring(1));return str.charAt(0) + pairStar(str.substring(1));}// Given a string, compute recursively a new string where all the lowercase 'x' chars have been moved to the end of the string.publicString endX(String str){if(str.length() ==0)return str;if(str.charAt(0) =='x')return endX(str.substring(1)) +'x';return str.charAt(0) + endX(str.substring(1));}// We'll say that a "pair" in a string is two instances of a char separated by a char. So "AxA" the A's make a pair. Pair's can overlap, so "AxAxA" contains 3 pairs -- 2 for A and 1 for x. Recursively compute the number of pairs in the given string.publicint countPairs(String str){if(str.length() <3)return0;if(str.charAt(0) == str.charAt(2))return1+ countPairs(str.substring(1));return countPairs(str.substring(1));}// Count recursively the total number of "abc" and "aba" substrings that appear in the given string.publicint countAbc(String str){String left;if(str.length() <3)return0; left = str.substring(0, 3);if(left.equals("abc"))return1+ countAbc(str.substring(3));if(left.equals("aba"))return1+ countAbc(str.substring(2));return countAbc(str.substring(1));}// Given a string, compute recursively (no loops) the number of "11" substrings in the string. The "11" substrings should not overlap.publicint count11(String str){if(str.length() <2)return0;if(str.substring(0, 2).equals("11"))return1+ count11(str.substring(2));return count11(str.substring(1));}// Given a string, return recursively a "cleaned" string where adjacent chars that are the same have been reduced to a single char. So "yyzzza" yields "yza".publicString stringClean(String str){if(str.length() <2)return str;if(str.charAt(0) == str.charAt(1))return stringClean(str.substring(1));return str.charAt(0) + stringClean(str.substring(1));}// Given a string, compute recursively the number of times lowercase "hi" appears in the string, however do not count "hi" that have an 'x' immedately before them.publicint countHi2(String str){if(str.length() <2)return0;if(str.length() ==2)return (str.equals("hi")) ?1:0;if(str.charAt(0) =='x') {if(str.substring(1, 3).equals("hi"))return countHi2(str.substring(3));return countHi2(str.substring(1)); }if(str.substring(0, 2).equals("hi"))return1+ countHi2(str.substring(2));if(str.substring(1, 3).equals("hi"))return1+ countHi2(str.substring(3));return countHi2(str.substring(2));}// Given a string that contains a single pair of parenthesis, compute recursively a new string made of only of the parenthesis and their contents, so "xyz(abc)123" yields "(abc)". publicString parenBit(String str){int len = str.length();if(str.charAt(0) !='(') {if(str.charAt(len -1) !=')')return parenBit(str.substring(1, len -1));return parenBit(str.substring(1)); }if(str.charAt(len -1) !=')')return parenBit(str.substring(0, len -1));return str;}// Given a string, return true if it is a nesting of zero or more pairs of parenthesis, like "(())" or "((()))". Suggestion: check the first and last chars, and then recur on what's inside them.publicboolean nestParen(String str){int len = str.length();if(len ==0)returntrue;if(str.charAt(0) =='('&& str.charAt(len -1) ==')')return nestParen(str.substring(1, len -1));returnfalse;}// Given a string and a non-empty substring sub, compute recursively the number of times that sub appears in the string, without the sub strings overlapping.publicint strCount(String str, String sub){int sLen = sub.length();if(str.length() < sLen)return0;if(str.substring(0, sLen).equals(sub))return1+ strCount(str.substring(sLen), sub);return strCount(str.substring(1), sub);}// Given a string and a non-empty substring sub, compute recursively if at least n copies of sub appear in the string somewere, possibly with overlapping. N will be non-negative. publicboolean strCopies(String str, String sub, int n){if(n ==0)returntrue;if(str.length() < sub.length())returnfalse;if(str.substring(0, sub.length()).equals(sub))return strCopies(str.substring(1), sub, n -1);return strCopies(str.substring(1), sub, n);}// Given a string and a non-empty substring sub, compute recursively the largest substring which starts and ends with sub and return its length. publicint strDist(String str, String sub){int stLen = str.length();int sbLen = sub.length();if(stLen < sbLen)return0;if(str.substring(0, sbLen).equals(sub)) {if(str.substring(stLen - sbLen, stLen).equals(sub))return stLen;return strDist(str.substring(0, stLen -1), sub); }return strDist(str.substring(1), sub);}

---

For further help with Coding Bat (Java), please check out my books. I am also available for tutoring.

---

Recursion is neat in theory and commonly leads to very clean code. Some people have a hard time understanding it, though. If you’ve ever encountered a recurrence relation in mathematics, then you already know everything there is to know about the “mind-bending” nature of recursive problems.

Otherwise, try this simple strategy. First, you may be tempted to think recursively about recursive functions. This may work with factorials, but for something more complex like, say, the Ackermann function, it’s a recipe for disaster. So, don’t do it! Instead, figure out what the base case consists of. The base case immediately returns a result. All other conditions eventually have to revert to the base case, which means that you’ll return “something” in addition to recursively calling the function, but with an input that brings you closer to the base case.

The first example, factorial, of CodingBat’s Recursion-1 section illustrates this strategy very well. All subsequent problems are rather similar.

All solutions were successfully tested on 24 March 2013.

factorial:

public int factorial(int n) { if (n <= 1) return 1; return n * factorial(n - 1); }

bunnyEars:

public int bunnyEars(int bunnies) { if (bunnies == 0) return 0; return 2 + bunnyEars(bunnies - 1); }

fibonacci:

public int fibonacci(int n) { if (n <= 1) return n; return fibonacci(n - 2) + fibonacci(n - 1); }

bunnyEars2:

public int bunnyEars2(int bunnies) { if (bunnies == 0) return 0; if (bunnies % 2 == 1) return 2 + bunnyEars2(bunnies - 1); return 3 + bunnyEars2(bunnies - 1); }

triangle:

public int triangle(int rows) { if (rows == 0) return 0; return rows + triangle(rows - 1); }

sumDigits:

public int sumDigits(int n) { if (n == 0) return 0; return n % 10 + sumDigits(n / 10); }

count7:

public int count7(int n) { if (n == 0) return 0; if (n % 10 == 7) return 1 + count7(n / 10); return count7(n / 10); }

count8:

public int count8(int n) { if (n == 0) return 0; if (n >= 88 && n % 100 == 88) return 2 + count8(n / 10); if (n % 10 == 8) return 1 + count8(n / 10); return count8(n / 10); }

powerN:

public int powerN(int base, int n) { if (n == 0) return 1; return base * powerN(base, n - 1); }

countX:

public int countX(String str) { if (str.length() == 0) return 0; if (str.charAt(0) == 'x') return 1 + countX(str.substring(1)); return countX(str.substring(1)); }

---

For further help with Coding Bat (Java), please check out my books. I am also available for tutoring.

---

Recursion-1

CODING BAT ANSWERS IS MOVING TO A NEW AND IMPROVED SITE, PLEASE CLICK HERE TO VIEW SOLUTIONS TO EVERY JAVABAT PROBLEM AND LEARN FROM MY MISTAKES!!!!

This section includes these questions: factorial, bunnyEars, fibonacci, bunnyEars2, triangle, sumDigits, count7, count8, powerN, countX, countHi, changeXY, changePi, noX, array6, array11, array220, allStar, pairStar, endX countPairs, countAbc, count11, stringClean, countHi2, parenBit, nestParen, strCount, strCopies, strDist.

factorial

public int factorial(int n) { if( n == 1) { return 1; } else { return factorial(n-1) * n; } }

bunnyEars

public int bunnyEars(int bunnies) { if( bunnies == 0 ) return 0; else return bunnies + bunnies; }

fibonacci

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

bunnyEars2

public int bunnyEars2(int bunnies) { if( bunnies == 0) return 0; else return bunnies + bunnies + (bunnies / 2); }

triangle

public int triangle(int rows) { if ( rows == 0) return 0; if (rows == 1) return 1; else return triangle(rows - 1) + rows; }

sumDigits

public int sumDigits(int n) { int sum; if ( n == 0) return 0; else { sum = n % 10; n = n / 10; return sumDigits( n) + sum; } }

count7

public int count7(int n) { int sum; if( n == 0) return 0; else { sum = n % 10; n = n / 10; if (sum == 7) return 1 + count7(n); else return count7(n); } }

count8

public int count8(int n) { int sum; if ( n == 0) return 0; else { sum = n % 10; n = n / 10; if ( sum == 8 && n % 10 == 8 ) return 2 + count8(n); if ( sum == 8) return 1 + count8(n); else return count8(n); } }

powerN

public int powerN(int base, int n) { if ( n == 1) return base; if ( n == 0) return 0; else return base * powerN( base, n - 1); }

countX

public int countX(String str) { int result = 0; if(str.length() == 0) { return 0; } if(str.charAt(0) == 'x') { result++; } result += countX(str.substring(1, str.length())); return result; }

countHi

public int countHi(String str) { int result = 0; if(str.length() <= 2) { if(str.equals("hi")) { return 1; } return 0; } if(str.substring(0, 2).equals("hi")) { result++; str = str.substring(2, str.length()); } else { str = str.substring(1, str.length()); } result += countHi(str); return result; }

changeXY

public String changeXY(String str) { String result = ""; if(str.length() == 0) { return ""; } if(str.charAt(0) == 'x') { result = "y"; } else { result = Character.toString(str.charAt(0)); } return result + changeXY(str.substring(1, str.length())); }

changePi

public String changePi(String str) { String result = ""; if(str.length() < 2) { return str; } if(str.charAt(0) == 'p' && str.charAt(1) == 'i') { result = "3.14"; str = str.substring(2, str.length()); } else { result = Character.toString(str.charAt(0)); str = str.substring(1, str.length()); } return result + changePi(str); }

noX

public String noX(String str) { String result = ""; if(str.length() == 0) { return ""; } if(str.charAt(0) == 'x') { result = ""; } else { result = Character.toString(str.charAt(0)); } return result + noX(str.substring(1, str.length())); }

array6

public boolean array6(int[] nums, int index) { if(index >= nums.length) { return false; } else if(nums[index] == 6) { return true; } else { return array6(nums, index + 1); } }

array11

public int array11(int[] nums, int index) { int result = 0; if(index >= nums.length) { return 0; } if(nums[index] == 11) { result++; } result += array11(nums, index + 1); return result; }

array220

public boolean array220(int[] nums, int index) { if(index >= nums.length - 1) { return false; } else if(nums[index] * 10 == nums[index + 1]) { return true; } else { return array220(nums, index + 1); } }

allStar

public String allStar(String str) { String result = ""; if(str.length() == 1 || str.length() == 0) { return str; } else { result += (Character.toString(str.charAt(0)) + "*"); } result += allStar(str.substring(1, str.length())); return result; }

pairStar

public String pairStar(String str) { String result = ""; if(str.length() <= 1) { return str; } if(str.charAt(0) == str.charAt(1)) { result += (Character.toString(str.charAt(0)) + "*"); } else { result += Character.toString(str.charAt(0)); } result += pairStar(str.substring(1, str.length())); return result; }

endX

public String endX(String str) { String result = ""; int x = countX(str); result = removeX(str); result += addX(x); return result; } public int countX(String str) { int x = 0; if(str.length() <= 0) { return 0; } if(str.charAt(0) == 'x') { x++; } x += countX(str.substring(1, str.length())); return x; } public String removeX(String str) { String result = ""; if(str.length() <= 0) { return ""; } else if(str.charAt(0) == 'x') { result += ""; } else { result += Character.toString(str.charAt(0)); } result += removeX(str.substring(1, str.length())); return result; } public String addX(int num) { if(num < 1) { return ""; } if(num == 1) { return "x"; } return "x" + addX(num - 1); }

countPairs

public int countPairs(String str) { int result = 0; if(str.length() <= 2) { return 0; } if(str.charAt(0) == str.charAt(2)) { result++; } result += countPairs(str.substring(1, str.length())); return result; }

countAbc

public int countAbc(String str) { int result = 0; if(str.length() <= 2) { return 0; } if(str.substring(0, 3).equals("aba") || str.substring(0, 3).equals("abc")) { result++; } result += countAbc(str.substring(1, str.length())); return result; }

count11

public int count11(String str) { int result = 0; if(str.length() <= 1) { return 0; } if(str.substring(0, 2).equals("11") || str.substring(0, 2).equals("11")) { result++; str = str.substring(2, str.length()); } else { str = str.substring(1, str.length()); } result += count11(str); return result; }

stringClean

public String stringClean(String str) { if(str.length() <= 1) { return str; } String result = "", c = Character.toString(str.charAt(0)), n = ""; do { if(n.equals(c)) { str = str.substring(1, str.length()); if(str.length() <= 1) { break; } } n = Character.toString(str.charAt(1)); } while(n.equals(c) && str.length() > 1); if(str.length() < 1) { } else { str = str.substring(1, str.length()); } result += c; result += stringClean(str); return result; }

countHi2

public int countHi2(String str) { int result = 0; if(str.length() < 2) { return 0; } else if(str.length() == 2) { if(str.equals("hi")) { return 1; } else { return 0; } } else { if(str.charAt(0) == 'x') { if(str.length() <= 3) { return 0; } else if(str.substring(1, 3).equals("hi")) { str = str.substring(3, str.length()); } else { str = str.substring(1, str.length()); } } else { if(str.substring(0, 2).equals("hi")) { result++; str = str.substring(2, str.length()); } else { str = str.substring(1, str.length()); } } } result += countHi2(str); return result; }

parenBit

public String parenBit(String str) { String result = ""; if(str.charAt(0) == '(') { if(str.charAt(str.length() - 1) == ')') { return str; } else { return parenBit(str.substring(0, str.length() - 1)); } } else { return parenBit(str.substring(1, str.length())); } }

nestParen

public boolean nestParen(String str) { String result = ""; if(str.length() == 0) { return true; } if(str.length() < 1) { return false; } if(str.charAt(0) == '(') { if(str.charAt(str.length() - 1) == ')') { return nestParen(str.substring(1, str.length() - 1)); } return false; } else { return false; } }

strCount

public int strCount(String str, String sub) { int result = 0; if(str.length() < sub.length()) { return 0; } else if(str.length() == sub.length() && str.equals(sub)) { return 1; } else if(str.substring(0, sub.length()).equals(sub)) { result++; str = str.substring(sub.length(), str.length()); } else { str = str.substring(1, str.length()); } result += strCount(str, sub); return result; }

strCopies

public boolean strCopies(String str, String sub, int n) { if(strCount(str, sub) == n) { return true; } else { return false; } } public int strCount(String str, String sub) { int result = 0; if(str.length() < sub.length()) { return 0; } else if(str.length() == sub.length() && str.equals(sub)) { return 1; } else if(str.substring(0, sub.length()).equals(sub)) { result++; } str = str.substring(1, str.length()); result += strCount(str, sub); return result; }

strDist

public int strDist(String str, String sub) { if(str.length() == 1 && str.equals(sub)) { return 1; } else if(str.length() < sub.length() || str.length() <= 1) { return 0; } else { if(str.charAt(0) == sub.charAt(0) && str.charAt(0) == str.charAt(str.length() - sub.length()) && str.substring(str.length() - sub.length(), str.length()).equals(sub) && str.substring(str.length() - sub.length()).equals(sub)) { return str.length(); } else { if(str.substring(0, sub.length()).equals(sub)) { return strDist(str.substring(0, str.length() - 1), sub); } else if(str.substring(str.length() - sub.length(), str.length()).equals(sub)) { return strDist(str.substring(1, str.length()), sub); } return strDist(str.substring(1, str.length() - 1), sub); } } }

This section includes these questions: factorial, bunnyEars, fibonacci, bunnyEars2, triangle, sumDigits, count7, count8, powerN, countX, countHi, changeXY, changePi, noX, array6, array11, array220, allStar, pairStar, endX countPairs, countAbc, count11, stringClean, countHi2, parenBit, nestParen, strCount, strCopies, strDist.