**w.substring(natural i,natural j) returns the substring consisting consisting of the characters with the position k such that i<= kk < j**

we already have valid recursive algorithm for these that we can use, below:

boolean isZero (natural x) // Returns true if and only if x is zero natural successor (natural x) // Returns the successor of x natural pred (natural x) // Returns the predecessor of x, if x is not zero // Throws an exception if x is zero pred(successor(x)) == x if !isZero(x), successor(pred(x)) == x public natural plus (natural x, natural y) { if (isZero(y)) return x; return successor (plus (x, pred(y));} public natural minus (natural x, natural y) { If(x>y) return 0; // return y - x} public natural times (natural x, natural y) { if (isZero(y) return 0; return plus( times(x, pred(y)), x);} public static boolean isEmpty( ){...} public static string append (string w, char a) {...} public static char last (string w) {...} public static string allButLast (string w) {...} public static natural length (string w) { if (isEmpty(w)) return 0; return successor(length(allButLast(w)));} public static string cat (string w, string x) { if (isEmpty(x)) return w; return append(cat(w, allButLast(x)), last(x));} public static string rev (string w) { if (isEmpty(w)) return w; return cat(last(w), rev(allButLast(w)));}

After few (many) attempts, I have come up with this algorithm. Comments/suggestion? I am not allowed to answer this using Java program.

public static string substring(string w, natural i, natural j){ if(length(w) == minus(i,j)){ return w;} else { if((i >= length(w)||(i >= length(w)){throw exception;} elseif (i>=j){throw exception;} else{ return substring(rev(substring(allButLast(w)), i, j), i, j) } }

This post has been edited by **Atli**: 25 October 2013 - 09:02 AM

Reason for edit:: Replaced [b] tags around code with [code] tags.