Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Query on usage of this variable in Recursion

Tags:

java

recursion

After calling method,

node.nth(5)

in below code,

public class List_Node {
    int item;
    List_Node next;
    public List_Node() {
        this.item = 0;
        this.next = null;
    }
    public List_Node(int item, List_Node next) {
        this.item = item;
        this.next = next;
    }
    public List_Node(int item) {
        this(item, null);
    }
    public void insertAfter(int item) {
        this.next = new List_Node(item, this.next);
    }
    public List_Node nth(int position) {
        if (position == 1) {
            return this;
        } else if((position < 1) || (this.next == null)) {
        /* error checking */
            return null;
        } else {
            return this.next.nth(position - 1);
        }
    }
    public static void main(String[] args){
        List_Node node = new List_Node(0);
        List_Node temp = node;
        for (int item = 1; item < 5; item++) {
            temp.insertAfter(item);
            temp = temp.next;
        }
        System.out.println(node.nth(5).item);
    }
}

Below is the stack frame that I can imagine for nth() method after 4 recursive calls.

enter image description here

My question:

As per the above diagram, Assuming the instance of being in activation record S5 with value of pos as 1, I would like to understand, What happens, when java executes return this?
Does java assign the value of this in S5 as value of this in S4? Because there is no assignment statement (as such) in else{} block of nth() method.

Note: Please ignore Java coding style, as am new learner.

like image 814
overexchange Avatar asked Sep 10 '14 00:09

overexchange


People also ask

How are variables used in recursion?

The code works on the basic principle of recursion. Every time it does not find the element at the position it will keep incrementing the value of variable recS by 1 . If the element is not found and it reaches at the last element then it simply returns -1 .

How do you write a recursive query in SQL?

Recursion is achieved by WITH statement, in SQL jargon called Common Table Expression (CTE). It allows to name the result and reference it within other queries sometime later. Naming the result and referencing it within other queries.

How do you write a recursive query in DB2?

DB2® for i provides two ways of defining a recursive query. The first one is called a hierarchical query which uses the CONNECT BY clause to define how a parent row is to be associated with its child rows. The second method is to use a recursive common table expression.

What is recursive query in SQL Server?

A recursive query is one that is defined by a Union All with an initialization fullselect that seeds the recursion. The iterative fullselect contains a direct reference to itself in the FROM clause. There are additional restrictions as to what can be specified in the definition of a recursive query.


1 Answers

Each time you call this.next.nth(), you are calling nth() method on a completely different object. Your this will refer to that new object (in previous stack it was next). Its not a pure recursion. Just think as if you are calling different method on some different object.

So when position=1 the this would refer to S5.

UPDATE Lets say your List_Nodes are chained like this 10->20->30->40->50

Whenever you call node.nth(5) from main,

Stack 1: position 5, this points to 10 (you are calling this.next.nth(4); means 20.nth())
    Stack 2: position 4, this points to 20 (calling this.next.nth(3); = 30.nth())
        Stack 3: position 3, this points to 30 (calling this.next.nth(2) = 40.nth())
            Stack 4: position 2, this points to 40 (calling this.next.nth(1) = 50.nth())
                Stack 5: position 1, this points to 50 (returning this; this here is 50)
                returns 50
            returns 50 (not going back into if, so return value remains same)
        returns 50
    returns 50
returns 50

The same this is depicted in a picture while discussing on chat. Adding it here, to benefit future reader. enter image description here

Another UPDATE

No assignment variable in else as such

You can write this like

List_Node temp = this.next.nth(position-1);
return temp;

In general, we need to separate List and Node classes, your List should have an head and your Node will have item and next pointer. Just like the LinkedList in java. Then the nth() method will be in List class and it just iterates through it until you reach the nth element.

like image 116
RP- Avatar answered Nov 15 '22 20:11

RP-