Add polynomials together using recursion

Question

I need to add two polynomials together using a recursive method. This is for a past-due assignment (I imagine a similar thing will be on a test). Main class:

public class Polynomial {

    private Node poly;


    public Polynomial(){
    poly = new Node();
    }

    private Polynomial(Node node){
    poly = node;
    }
    public void addTerm(int coef, int exp){
    Term term = new Term(coef, exp);
    Node node = new Node(term, null);

    Node iterator = poly;

    //if the list is empty just add the node
    if (poly.next == null){
        System.out.println("poly.next is null. adding node to first pos.");
        poly.next = node;
        return;
    }

    //if list isn't empty find the appropriate spot for it
    while (iterator.next != null){
        System.out.println("iterator.next != null...");
        if (exp < iterator.next.data.exp){
        System.out.println("\texp < iterator.next.data.exp");
        node.next = iterator.next;
        iterator.next = node;
        return;
        }
        if (exp == iterator.next.data.exp){
        System.out.println("\texp == iterator.next.data.exp");
        iterator.next.data.coef += coef;
        return;
        }
        iterator = iterator.next;
    }

    //if we get to this point then the list isn't empty
    //and it doesn't fit inside the list, hence it must
    //be added to the end of the list
    System.out.println("list wasn't empty, didn't fit inside");
    iterator.next = node;
    return;
    }

    @Override
    public String toString(){
    Node iterator = poly;
    String out = "";

    if (poly.next == null){
        return out;
    }
    while(iterator.next != null){
        out += iterator.next.data.coef;
        out += "*x^";
        out += iterator.next.data.exp;
        out += " + ";
        iterator = iterator.next;
    }
    return out.substring(0, out.lastIndexOf('+'));
    }



    public Polynomial addPolynomial (Polynomial that){
    Polynomial ret = new Polynomial();

    Polynomial iterator = this;

    return addPolynomial(that, ret, iterator);
    }

    public Polynomial addPolynomial(Polynomial that, Polynomial ret, Polynomial iterator){
    if (iterator.poly.next == null){
        return new Polynomial(that.poly);
    }

    if (that.poly.next == null){
        return new Polynomial(iterator.poly);
    }

    if (iterator.poly.next.data.exp < that.poly.next.data.exp){
        ret.addTerm(iterator.poly.next.data.coef, iterator.poly.next.data.exp);
        iterator.poly = iterator.poly.next;
        return iterator.addPolynomial(that);
    }

    if (iterator.poly.next.data.exp == that.poly.next.data.exp){
        ret.addTerm(iterator.poly.next.data.coef + that.poly.next.data.coef, iterator.poly.next.data.exp);
        iterator.poly = iterator.poly.next;
        that.poly = that.poly.next;
        return iterator.addPolynomial(that);
    }

    if (iterator.poly.next.data.exp > that.poly.next.data.exp){
        ret.addTerm(that.poly.next.data.coef, that.poly.next.data.exp);
        that.poly = that.poly.next;
        return iterator.addPolynomial(that);
    }
    return ret;
    }

    /*
     * Term
     */
    private class Term implements Comparable{
    int coef;
    int exp;

    public int getCoef() {
        return coef;
    }

    public void setCoef(int coef) {
        this.coef = coef;
    }

    public int getExp() {
        return exp;
    }

    public void setExp(int exp) {
        this.exp = exp;
    }

    public Term(int coef, int exp) {
        this.coef = coef;
        this.exp = exp;
    }
    public int compareTo(Object rhs){
        Term that = (Term)rhs;
        return this.exp - that.exp;
    }
    }//end Term


    /*
     * Node
     */
    private class Node{
    Term data;
    Node next;

    public Term getData() {
        return data;
    }

    public void setData(Term data) {
        this.data = data;
        this.next = null;
    }

    public Node getNext() {
        return next;
    }

    public void setNext(Node next) {
        this.next = next;
    }

    public Node() {
        this.data = null;
        this.next = null;
    }

    public Node(Term data, Node next) {
        this.data = data;
        this.next = next;
    }
    }//end Node




}

Test Class:

public class Polynomials {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        Polynomial p1 = new Polynomial();
        Polynomial p2 = new Polynomial();
        Polynomial p0 = new Polynomial();
        p1.addTerm(1, 2);
        p1.addTerm(1, 4);
        p1.addTerm(1, 6);
    p2.addTerm(1, 1);
    p2.addTerm(1, 3);
    p2.addTerm(1, 5);
    System.out.println("p1 = " + p1.toString());
    System.out.println("p2 = " + p2.toString());

    System.out.println("Adding p1 to p2...");
    p0 = p1.addPolynomial(p2);
    System.out.println(p0.toString());
    }
} 

Answer 1

Have you considered this way of doing it?

public class Polynomial {
public static void main(String[] args) {
    Polynomial p1 = new Polynomial();
    Polynomial p2 = new Polynomial();
    Polynomial p0 = new Polynomial();
    p1.addTerm(1, 2);
    p1.addTerm(1, 4);
    p1.addTerm(1, 6);
    p2.addTerm(1, 1);
    p2.addTerm(2, 3);
    p2.addTerm(2, 2);
    p2.addTerm(1, 5);
    System.out.println("p1 = " + p1.toString());
    System.out.println("p2 = " + p2.toString());

    System.out.println("Adding p1 to p2...");
    p0 = p1.addPolynomial(p2);
    System.out.println(p0.toString());

    for(int i = 0;i < 100;i++) {
        p1 = new Polynomial();
        p2 = new Polynomial();
        for(int j = 0;j < 4;j++) {
            p1.addTerm((int) (10 * Math.random()) - 5,
                    (int) (4 * Math.random()));
            p2.addTerm((int) (10 * Math.random()) - 5,
                    (int) (4 * Math.random()));
        }
        p0 = p1.addPolynomial(p2);
        System.out.println(p1 + "\n" + p2 + "\n" + p0 + "\n");
    }
}



enum Comp {
    LT, EQ, GT
}


static Comp cmp(int a, int b) {
    return (a < b) ? Comp.LT : (a == b) ? Comp.EQ : Comp.GT;
}

private Term poly;


public Polynomial() {
    poly = null;
}


public void addTerm(int coef, int exp) {
    if (coef == 0) return;
    Term term = new Term(coef, exp,null);
    if (poly == null) {
        poly = term;
    } else {
        poly = poly.add(term);
    }
}


@Override
public String toString() {
    if (poly == null) return "0";

    StringBuilder buf = new StringBuilder();
    poly.writeTo(buf);
    return buf.toString();
}


public Polynomial addPolynomial(Polynomial that) {
    Polynomial ret = new Polynomial();
    if (poly != null) {
        ret.poly = new Term(poly);
        if (that.poly != null) {
            ret.poly = ret.poly.add(new Term(that.poly));
        }
    } else if (that.poly != null) {
        ret.poly = new Term(that.poly);
    }
    return ret;
}


private class Term {
    final int coef;

    final int exp;

    final Term next;


    Term(int coef, int exp, Term next) {
        this.coef = coef;
        this.exp = exp;
        this.next = next;
    }


    Term(Term copy) {
        this.coef = copy.coef;
        this.exp = copy.exp;
        if (copy.next == null) {
            this.next = null;
        } else {
            this.next = new Term(copy.next);
        }
    }


    Term add(Term other) {
        if (other == null) return this;

        switch (cmp(this.exp, other.exp)) {
        case LT: {
            Term n = other.add(this);
            return n;
        }
        case GT: {
            if (next == null) {
                return new Term(coef,exp,other);
            }

            return new Term(coef,exp,next.add(other));
        }
        default: {
            Term n = (next==null) ? other.next : next.add(other.next);
            int nc = coef+other.coef;
            return (nc!=0) ? new Term(nc,exp,n) : n;
        }
        }
    }


    public void writeTo(StringBuilder app) {
        if (coef != 1 || exp == 0) app.append(coef);
        if (exp == 1) {
            app.append("x");
        } else if (exp != 0) {
            app.append("x^").append(exp);
        }
        if (next != null) {
            app.append('+');
            next.writeTo(app);
        }
    }
}
}

Answer 2

Well that's certainly a bit more complex than necessary.

So you want to add a Polynomial to an already existing one, i.e.: 4*x^2 + 4 to 5*x^4+x+5, which results in: 5*x^4+4*x^2+x+9

You could obviously simplify the problem quite a bit by just using an array, but it's also not that hard with a linked list, the code should look something like this:

You have two pointers one pointing to the current position in the polynomial we want to add values (term1) and another one in the one we want to add (term2), both initialized to the lowest entry in the linked list (which we assume is sorted according to the exponent).

while term1 != NULL && term2 != NULL do:
   term1 > term2:
      add term2 to list
      term2 = term2.next()
   term2 > term1:
      term1 = term1.next()
   term1 = term2:
      add term2 to term1
      term1 = term1.next()
      term2 = term2.next()
while term1 == NULL && term2 != NULL:
   add term2
   term2 = term2.next()   

You can easily adapt that to also create a new polynomial instead of adding one to the other.

Okay so a little bit more details on how to turn the iterative solution into a recursive one: The first thing you always have to do when thinking about recursion is your exit condition.

In this case if you think about that's easy: We only do work as long as term2 is not NULL, as soon as term2 is NULL we're finished.

The next step is thinking about a good method signature and that's also quite easy this time, since we only need the two terms, so you can just use the two iterators: void addTogether(Iterator term1, Iterator term2); (assuming you're using an interface that's similar to the ListIterator, since you need to insert at the position before term1 - there are several ways to implement that)

ANd now you've just got to get rid of the while loops and replace them with a recursive call (in which you distinguish the different cases, do the necessary action and call it again)