9. (a) (6 points) Computational problem solving: Algorithm design: Describe a re

Question

9. (a) (6 points) Computational problem solving: Algorithm design: Describe a recursive algorithm to reverse a string that uses the strategy of swapping the first and last characters and recursively reversing the rest of the string. Assume the string is passed to the algorithm as an array A of characters, A[p...q], where the array has starting index p and ending index q, and the length of the string is n=q-p+1. The algorithm should have only one base case, when it gets an empty string. Assume you have a swap(A[i],A[j]) function available that will swap the characters in cells i and j. Write the algorithm using pseudocode without any programming language specific syntax. Your algorithm should be correct as per the technical definition of correctness. (b) (8 points) Draw your algorithm's recursion tree on input string ''i

Explanation / Answer

public class ReverseTest {

public static String reverse (String s) {

     if(s.length () <=1) return s;

      return reverse (s.substring (1, s.length())) + s.charAt (0);

}

public static void main (String[] args) {

// First check to see that there is atleast one command line argument

if (args.length==0) {

System.out.println ("Usage: ReverseTest <aString>");

System.exit(-1);

}

System.out.println (args[0] + "reversed is" + reverse (args[0]));

}

}

Reversing A string using Recursion

package.com.javacodegeeks.core.string;

public class StringReverseExample {                                                                                                                  String str= "Java";                                                                                                                                         String reverseStr= reverserRecursive(str);                                                                                          System.out.println("Normal string is" + str + " Reverse string is:" + reverseStr);

}

public static String reverseRecursive(string str) {

if(str.length() <= 1) {

return (str);

}

return reverseRecursive(str.substring(1)) + str.charAt(0);

} }

this will output

Normal string is: JAVA

Reverse string is: AVAJ

Answer(b) :- 1st call - reverseRecursive("

" )

will return: reverseRecursive("

" ) +"i"

2nd call :- reverseRecursive("

")

will return : reverseRecursive ("

") +"<"

3rd call :- reverseRecursive ("

") : will return : reverseRecursive("

") + "3"

4th call : reverseRecursive("

") will return : reverseRecursive("

") +"3"

5th call : reverseRecursive("

") will return : reverseRecursive("

") + "2"

6th call : reverseRecursive("

") will return : reverseRecursive("

") + "7"

7th call : reverseRecursive("

") will return : reverseRecursive("

") + "0"

8th call : reverseRecursive("

") will return: reverseRecursive ("

")

7th call : will return : reverseRecursive("

") + "0" = "!" + "0"

6th call : will return : reverseRecursive("

") + "7" ="!" + "0" + "7"

5th call : will return : reverseRecursive("

") + "2" = "!" + "0" + "7" +"2"

4th call :will return : reverseRecursive("

") + "3" = "!" + "0" +"7" +"2" +"3"

3rd call :will return : reverseRecursive("

") + "3" = "!" + "0" + "7" + "2" + "3" + "3"

2nd call : will return : reverseRecursive("

") + "<" = "!" + "0" + "7" + "2" + "3" + "3" + "<"

1st call : will return : reverseRecursive("

") + "i" = "!" + "0" + "7" + "2" + "3" + "3" + "<" + "i"

i < 3 3 2 7 0 !

Related Questions

Navigate

• Browse (All)
• Browse 9
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.