使用递归在Java中

我需要一个课堂作业写与指定的方法签名的方法双向链表找到最小的元素：使用递归在Java中

public static <T extends Comparable<T>> T findSmallest(DoubleLinkedListADT<T> list)

的方法必须返回列表中的最小元素，它必须递归，我不能修改方法签名，增长函数不能有超过n像个大O更大

这里是我到目前为止（O（nlogn）是不能接受的。）：

public static <T extends Comparable<T>> T findSmallest(DoubleLinkedListADT<T> list) { 

    if(list.isEmpty()){ 
     return null; 
    } 
    ListIterator<T> lit = list.listIterator(); 
    T smallest = lit.next(); 

    return search(lit, smallest); 
} 

private static <T extends Comparable<T>> T search(ListIterator<T> lit, T smallest){ 

    if(lit.hasNext()){ 
     if(smallest.compareTo(lit.next())==1){ 
      smallest = lit.previous(); 
      lit.next(); 
     } 
     search(lit, smallest); 
    } 
    return smallest; 
}

（不要担心DoubleLinkedListADT，它是一个老师提供的接口。可以将DoubleLinkedList引用分配给DoubleLinkedListADT类型，它是它的子节点。）

这适用于空列表，单个元素列表和两个元素列表。任何更大的东西都会失败。我想我只是不理解递归，因为我很困惑，因为搜索方法中的第一个return语句不是返回到调用findSmallest类中的搜索的事实。它使用搜索中的最后一个返回调用，它使用最小的最小对象引用。

我不是在找别人给我正确的代码。我想弄清楚为什么它在做什么。

来源

2015-05-01 Khaines0625

放弃任何东西，包括做功课和上大学，去尝试几个简单的递归函数来了解它们是如何工作的。 – pjsofts

findSmallest（list）= min（listHead，findSmallest（listTail））希望这个小提示能帮助:-) –

我会考虑的。 – Khaines0625

那么，你的代码是复杂的，所有双链接爬行看起来很讨厌。这里是最优雅的解决方案，我能来与整数的列表：

public class Test { 

    public static Integer min(Iterator<Integer> it) { 
     if (it.hasNext()) { 
      return Math.min(it.next(), min(it)); 
     } 
     return Integer.MAX_VALUE; 
    } 

    public static void main(String[] args) { 
     System.out.println(min(Arrays.asList(2, 3, 1, 4, 5).iterator())); 
    } 
}

它适应于任何类型的列表应该很容易。

来源

2015-05-01 20:41:10

这是有道理的。谢谢。我会看看我是否可以为我工作。 – Khaines0625

使用递归在Java中

回答

相关问题