Create a list with following numbers (recursive)

Question

I need the function to return a list with following numbers so follow(null, 5); should return [1, 2, 3, 4, 5]

I tried this:

public static Node <Integer> follow(Node<Integer>list, int num)
{
    if(num==1)
        return new Node<Integer>(1);
    return new Node<Integer>(num, follow(list, num-1));
}

but this returns [5, 4, 3, 2, 1] instead of [1, 2, 3, 4, 5] what do I need to change in the function so it will return [1, 2, 3, 4, 5]? (I dont want to add another functions)

This is the Node Class:

package unit4.collectionsLib;

public class Node<T>
{
    private T info;
    private Node<T> next;

    public Node(T x)
    {
        this.info = x;
        this.next = null;
    }

    public Node(T x, Node<T> next)
    {
        this.info = x;
        this.next = next;
    }

    public T getValue()
    {
        return(this.info);
    }



}

You don't need our help for this, you have all the information you need already. Look at your code: why would it be putting lower numbers to the right, instead of left, of higher numbers? (take a pencil and some paper, and literally write out what happens at every single step when you start with num=2) — Mike 'Pomax' Kamermans, Nov 26 '19 at 22:07
To add to Mike's comment: the issue is with the order of your recursion. — Code-Apprentice, Nov 26 '19 at 22:12
you can still work with the same implementation then reverse it's order, if it is an array. — Mohamed, Nov 26 '19 at 22:16
@yoav I suggest that you learn about tail recursion to help you solve this problem. — Code-Apprentice, Nov 27 '19 at 17:05
@Code-Apprentice if I use tail recursion will I need to add another variable? — yoav, Nov 27 '19 at 18:53
@yoav No, you won't need any new variables. You just need to change your `return` statements as I hint at in my answer. Please take some time to try to answer the two questions I ask there. — Code-Apprentice, Nov 27 '19 at 19:04
@Code-Apprentice I cant think of the solution I really tried. — yoav, Nov 27 '19 at 20:43
@yoav Start with the base case. Instead of creating a node with `1` as the end of the list, you need to create a node with `1` and then the rest of the list. Which `Node` constructor should you use to do this? — Code-Apprentice, Nov 27 '19 at 20:49
Let us [continue this discussion in chat](https://chat.stackoverflow.com/rooms/203206/discussion-between-yoav-and-code-apprentice). — yoav, Nov 27 '19 at 21:27

score 1 · Answer 1 · answered Nov 26 '19 at 22:24

1

You're counting down from 5 to 1 as you go deeper into recursion. What if you counted up from 1 to 5 as you went deeper into the recursion? What would the order be of the numbers?

To implement that, the maximum number (5 in your example) needs to be available at every recursion step, so you need an extra argument for that.

public static Node <Integer> follow(Node<Integer>list, int num, int max)
{
    if(num==max)
        return new Node<Integer>(max);
    return new Node<Integer>(num, follow(list, num + 1, max));
}

If you still want to have the convenience available of calling without passing the extra argument, you can overload the method by adding a convenience version of it:

public static Node <Integer> follow(Node<Integer>list, int max)
{
    return follow(list, 1, max);
}

answered Nov 26 '19 at 22:24

Erwin Bolwidt

30,799
15
56
79

1

This solution changes the signature of the function. There is a tail-recursive solution that leaves the signature the same. (And the compiler might be able to optimize out the recursion.) – Code-Apprentice Nov 26 '19 at 22:25
@Code-Apprentice It doesn't change the signature of the function if you add the overloaded method. You can even make the first method private. It's a very common way of doing recursion - because the recursive step may need extra parameters (accumulators, as in this case, or collectors, that are not present on the public method) – Erwin Bolwidt Nov 26 '19 at 22:38
1

Yes, this is a common tool for recursion. In this particular case, it is unnecessary. The return statements in the original code can be modified to get the desired behavior without introducing a helper function. – Code-Apprentice Nov 26 '19 at 22:40

score 0 · Accepted Answer · answered Nov 26 '19 at 22:18

0

public static Node <Integer> follow(Node<Integer>list, int num)
{
    if(num==1)
        return new Node<Integer>(1);

In your base case, you are creating a node with the smallest number. How can you change this to put the smallest number at the front of the list?

    return new Node<Integer>(num, follow(list, num-1));

In the recursive case, you are adding the current number at the front of the list. How can you change this to add the current number at the end?

answered Nov 26 '19 at 22:18

Code-Apprentice

81,660
23
145
268

So how would you add the current number to the end of the list? That's the crux of the question. As is done often in list-processing, the list is defined as a single-element head and a tail that is in itself a list. It's not trivial to add a single element to the end of a list this way in a recursive manner. – Erwin Bolwidt Nov 26 '19 at 22:40
@ErwinBolwidt "So how would you add the current number to the end of the list?" The solution is to switch around the nesting of the recursive call to `follow()` and the creation of a `new Node()`. – Code-Apprentice Nov 26 '19 at 22:56
@ErwinBolwidt Maybe my wording is poorly chosen. I guess you don't really "add the current number to the end of the list". Instead you add it in front of the `list` parameter passed in rather than in front of the return from a recursive call to `follow()`. – Code-Apprentice Nov 26 '19 at 23:03
@ErwinBolwidt In pseudocode it is the difference between building `follow(follow(follow(3)), 2), 1)` vs `follow(follow(follow(1), 2), 3)`. – Code-Apprentice Nov 26 '19 at 23:07
1

That means that you have a list as the head and a single item as the tail. There are very few algorithms that work with that (actually, effectively you have just said "iterate through the list in reverse order" because changing the order of the constructor arguments doesn't change the data structure). And it's very inefficient to traverse a head|tail list backward as it requires recursion to even the first element. – Erwin Bolwidt Nov 27 '19 at 06:31
@Code-Apprentice I dont understand the solution can you please write it? – yoav Nov 27 '19 at 10:39
@ErwinBolwidt "That means that you have a list as the head and a single item as the tail." That depends on the `Node` class itself and its constructor, not the `follow()` algorithm. I have a working solution on repl.com, but am hesitant to post it here since I don't feel like doing someone's homework for them. – Code-Apprentice Nov 27 '19 at 16:41
@yoav Think about the two questions I wrote in my answer here. How can you modify the base case so that the `1` is placed at the beginning of the `list` instead of at the end? – Code-Apprentice Nov 27 '19 at 16:42
@ErwinBolwidt Specifically, we can use [tail recursion](https://stackoverflow.com/questions/33923/what-is-tail-recursion) for an elegant solution that only modifies the two `return` statements from the original code in the question. Not only will the code remain as 5 lines, but most modern compilers can optimize out the recursive calls. – Code-Apprentice Nov 27 '19 at 16:52
@ErwinBolwidt One way to think of this is that you need to build the list as you call `follow()` recursively rather than as you return from each call as the OP is doing. – Code-Apprentice Nov 27 '19 at 17:00

Shar1er80 · Answer 3 · 2019-11-27T14:55:49.363

UPDATE

Given the limitation you commented, you could start with a node set to 1 and count up.

package stackoverflow;

public class Question {
    public static void main (String [] args){
        Node<Integer> list = new Node<Integer>(1);
        list.setNext(follow(list, 5));
        print(list);
    }

    public static Node <Integer> follow(Node<Integer>list, int num)
    {
        if(list.getValue() == num)
            return null;

        Node<Integer> nextNode = new Node<Integer>(list.getValue()+1);
        nextNode.setNext(follow(nextNode, num));
        return nextNode;
    }

    public static void print(Node<Integer> list) {
        System.out.println(list.getValue());
        if (list.next == null) {
            return;
        }

        print(list.next);
    }

    public static class Node<T>
    {
        private T info;
        private Node<T> next;

        public Node(T x)
        {
            this.info = x;
            this.next = null;
        }

        public Node(T x, Node<T> next)
        {
            this.info = x;
            this.next = next;
        }

        public T getValue()
        {
            return(this.info);
        }

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

RESULT

OLD ANSWER

Not the cleanest solution, but given what's being asked you could calculate the info field in the follow method. I used a class variable max to know how large the list needs to be

package stackoverflow;

public class Question {
    static int max = 5;
    public static void main (String [] args){
        Node<Integer> list = follow(null, max);
        print(list);
    }

    public static Node <Integer> follow(Node<Integer>list, int num)
    {
        int calculatedInfo = max - (num - 1);
        if(calculatedInfo == max)
            return new Node<Integer>(max);
        return new Node<Integer>(calculatedInfo, follow(list, num-1));
    }

    public static void print(Node<Integer> list) {
        System.out.println(list.info);
        if (list.next == null) {
            return;
        }

        print(list.next);
    }

    public static class Node<T>
    {
        private T info;
        private Node<T> next;

        public Node(T x)
        {
            this.info = x;
            this.next = null;
        }

        public Node(T x, Node<T> next)
        {
            this.info = x;
            this.next = next;
        }

        public T getValue()
        {
            return(this.info);
        }
    }
}

RESULT

RESULT MAX = 10

The function needs to work with num and list and no more variables. — yoav, Nov 27 '19 at 14:11
@yoav Edit your question and explain what your requirements are. Your comment is not mentioned in your question as a limitation. — Shar1er80, Nov 27 '19 at 14:30
I am not sure this solution is recursive because you must call the function with the max variable. — yoav, Nov 27 '19 at 14:44
@yoav The code calls follow within follow, how is that not recursion? See updated answer. — Shar1er80, Nov 27 '19 at 14:56

yoav · Answer 4 · 2019-11-28T13:35:45.760

0

public static Node <Integer> follow(Node<Integer>list, int num)
{
    if(num==1)
        return new Node<Integer>(num, list);
    return follow(new Node<Integer>(num, list), num-1);
}

This returns [1, 2, 3, 4, 5]

edited Nov 28 '19 at 13:35

answered Nov 28 '19 at 13:29

yoav

324
4
22

Create a list with following numbers (recursive)

4 Answers4