CODEWITHSUNDEEP
java
Renya Karasuma
Renya Karasuma

Reputation: 1060

the sum of two Linked Lists

A class Nat represents a Number (n) by having pre field which points to the n-1 number, if pre is null it means the number is zero.

public class Nat { 

     private final Nat pre; 
     public Nat (Nat pre) { this.pre = pre; } 
     public Nat () { this(null); } 
     public boolean isZero () { return pre == null; } 
     public Nat succ () { return new Nat(this); } 

     … 
    }

and I have to add a method which adds two numbers, I dont understand how this suppose to return a Nat which represents the sum of "this" and other!

public Nat plus (Nat other) { 

 if (other.isZero()) 
 return this; 

 return succ().plus(other.pre); 
}

I think it creates a "Nats" which point to the second Nat of this (pre) all the time.. Could any one help me please?

Upvotes: 4

Views: 196

Answers (4)

ROMANIA_engineer
ROMANIA_engineer

Reputation: 56626

This recursion is easier to understand in a functional language.

I am sure that other posts are clear enough for plus (a+b becomes a+1+b-1).

What it has to be clear is related to this part:

 public Nat (Nat pre) { this.pre = pre; } 
 ...
 public Nat succ () { return new Nat(this); }

When succ() is called, it returns a new Object, so this from here:

 public Nat succ () { return new Nat(this); }

will be pre from here:

 public Nat (Nat pre) { this.pre = pre; }

This is why that succ works because there will be something like this.pre.pre....pre at the end.

To understand better, you can type this (eventually add some print lines in your methods):

public static void main(String[] args) {
    System.out.println("==== A new number is 0 ====");
    Nat n1 = new Nat();                 // 0 
    System.out.println(n1.isZero());    // true
    Nat n2 = new Nat();                 // 0
    System.out.println(n2.isZero());    // true
    Nat sum = n1.plus(n2);              // 0
    System.out.println(sum.isZero());   // true
    System.out.println(n2.isZero());    // true
    System.out.println("==== Test succ and pre ====");
    Nat one = n1.succ();                // 1
    System.out.println(one.isZero());   // false
    Nat two = one.plus(one);            // 1 + 1
    System.out.println(two.isZero());   // false
    System.out.println(two.pre.isZero());       // false
    System.out.println(two.pre.pre.isZero());   // true
}

Upvotes: 0

Gil Vegliach
Gil Vegliach

Reputation: 3562

  • It is similar to tail recursion

Basically it unrolls the equation

n + k = (n + 1) + (k - 1)

Until k is zero. In the process a lot of temporary Nats are created but the final result is the Nat where the other Nat addend is zero: you kind of accumulates the result in the first Nat. Write down a simple execution of the algorithm with all the calls and you will see it.

Example: 1 + 2

1.plus(2)
-- 1.succ().plus(1)
---- 1.succ().succ().plus(0)
------> 1.succ().succ() == 3

EDIT: contrary to the other posts, I think this is not strictly speaking a recursive recursion. In fact the plus() method is not called always on the same object instance. The behavior is indeed recursive though. Then it depends on your definitions

Upvotes: 1

Mateusz Dymczyk
Mateusz Dymczyk

Reputation: 15141

You don't store the numbers directly in the list and create it recursively:

  1. [null] -> 0
  2. [null -> Nat1(pre=null)] -> 1
  3. [null -> Nat1(pre=null) -> Nat2(pre=Nat1)] -> 2
  4. etc

Why the plus() works:

Now we can observe that addition x+y can be changed to (x-1)+(y+1) etc. until 0 + (y + x). In your code you are not really interested in addition per se but you want to get to the Nat which represents the result of the summation. You do that recursively by using the above transformation until other is 0 - this is your base case which simply counts the recursive calls and makes sure you do them x times.

Example: 

[null -> Nat1(pre=null) -> Nat2(pre=Nat1) -> Nat3(pre=Nat2) -> Nat4(pre=Nat3) -> Nat5(pre=Nat5)]

And let's say you want to add 3 and 2. First you start with other=Nat2 and call it on Nat3, so you get Nat3's successor which is Nat4 and call plus() on it using other's predecessor which is Nat1, still no zero so you call plus() on Nat4's successor (Nat5) with Nat1's predecessor which is null, you hit your base case and return this which at this point of recursion is Nat5.

Upvotes: 1

Eran
Eran

Reputation: 393781

Well, if this represents n and other represents m, to calculate n + m is equivant to calculating n+1 + m-1, which is exactly what succ().plus(other.pre) returns.

At the end of the recurssion, the first number reaches n+m and the second number reaches 0. That's why you return this when other.isZero() is true.

Upvotes: 4

Related Questions