Minimum value in a Linked List. Incorrect recursive result?

Question

Trying to brush up on some concepts. I am trying to find the minimum value present amongst all Nodes in a Linked List implementation. I think for some reason my code is returning all the recursive return values, instead of only the last one. Can somebody check please what looks to be the issue in my findMin method?

public class Node
{
    public int data;
    public Node next;
    public Node(int d)
    {
        data = d;
        next = null;
    }
}



public static int findMin(Node head,int min=0)
{
    if (min == 0)
        min = head.data;
    if (head.data < min)
    {
        min = head.data;
    }
    else
    {
        findmin(head.next, min);
    }
    return min;
}

Not directly related to the question itself, but why use `0`as default for `min`? I assume it should be `int.MaxValue`, since you are attempting to find the smallest element in the list. — TerraPass, Jul 25 '16 at 10:55
Also, it's not entirely clear what you mean by "I think for some reason my code is returning all the recursive return values, instead of only the last one." Maybe provide an example of what `findMin()` returns for a given list of numbers? — TerraPass, Jul 25 '16 at 10:57
Is C# car insensitive? Where are you using the result (the possible min value) returned by `findmin`? — Sylwester, Jul 25 '16 at 11:02
Am I right in thinking that you are using recursion rather than looping for educational purposes? Because if not, you should not be using recursion to solve this. — Matthew Watson, Jul 25 '16 at 11:15
That's true @MatthewWatson, just for self-learning. Also, I agree with other posters that min should not have been init to 0. I had used that as a quick check against my test input. — Saurabh Kumar, Jul 25 '16 at 11:30

score 1 · Answer 1 · answered Jul 25 '16 at 10:58

1

The response of the recursive call of findmin never gets assigned to min. So calling it like min = findmin(head.next, min); should fix your problem

answered Jul 25 '16 at 10:58

Manuel Zelenka

1,616
2
12
26

that's not going to fix the issue, there is a logic error, where recursion stops once a value less than `min` is found. Not to mention that `min` is initialised as zero. – Yerken Jul 25 '16 at 11:08

yu_sha · Accepted Answer · 2016-07-25T11:20:42.070

1

I believe it's going to return you the first element. Or sometimes crash.

if (min == 0) min = head.data; //true initially. min=first element
if (head.data < min) //false. We just assigned it, it does not get executed
{
    min = head.data;
}
else
{
    findmin(head.next, min); //this gets executed but result is ignored
}
return min; // return head.data that you assigned in the first line

This is very broken.

you forgot to assign result of findmin(head.next, min) to anything
Even if head.data < min you still need to check the rest of the list. So "else" is not required
you forgot to check if list is empty
initial value should be int.MaxValue. Not 0, and not 10000 as suggested above. Then you don't need this extra comparison (because anything is less than 100000)
It's better to put recursive call on the end to let compiler (or JIT) replace tail-recursion with a loop. Or just write a loop yourself.

Here's what it should be

public static int findMin(Node head,int min=int.MaxValue)
{
     if (head == null) return min;
     if (head.data < min) min = head.data;
     return findmin(head.next, min);
}

edited Jul 25 '16 at 11:20

answered Jul 25 '16 at 11:11

yu_sha

4,290
22
19

is C# tail-call optimised? In any case this should be the accepted answer :P – Yerken Jul 25 '16 at 11:18
I assumed it did but I was wrong. According to this: http://stackoverflow.com/questions/7102520/does-c-sharp-do-tail-recursion compiler does not do it but JIT optimizes these calls. – yu_sha Jul 25 '16 at 11:20
This worked. I now see the basic flaws in my implementation. Thanks! – Saurabh Kumar Jul 25 '16 at 11:28
@yu_sha, in your example code, what happens when head.data is not less than min? In that case there is nothing to return I think for the findmin method, so won't that be a problem sometimes? – Saurabh Kumar Jul 25 '16 at 11:37
Initially min is set to the default parameter value of int.MaxValue. If list is empty this is what gets returned. If list is not empty the first element is going to be less (or equal) to int.MaxValue. – yu_sha Jul 25 '16 at 11:39

score 0 · Answer 3 · answered Jul 25 '16 at 10:59

Some issues: 1. passing the min by value 2. min initialized as 0.

Try this instead

public static int findMin(Node cur) {
    if (cur == null) return 1000000;
    int next_min = findMin(cur.next)
    if (cur.data < next_min) return cur.data;
    return next_min;
}

Better to not use recursion here to save stack memory. Just use while loop and find the minimum.

Minimum value in a Linked List. Incorrect recursive result?

3 Answers3