Scala：递归地找到数组的最大值

我是scala新手。为了练习递归，我为自己设定了查找数组最大值的任务。我的基本情况是一个长度为1的数组。对于每个递归通道，我比较数组值0和1的大小，直到基本情况得到满足时消除较小的值。Scala：递归地找到数组的最大值

def max(m: Array[Int]): Int = { 
     if (m.length == 1) m(0) 
     else if (m(0) > m(1)) m.take(1) 
     else m.take(0) 
    return max(m) 
    }

但是，在repl中，这不会返回任何东西（可能是一个无限循环）。我不明白为什么数组没有减少到长度1.我是否需要次要的内部函数或什么？

来源

2017-02-26 RDJ

您也可以定义一个带有元素和current-max的本地函数。然后再次使用下一个元素和更新的current-max调用本地函数。 – rethab

这绝对是一个无限循环，因为你是递归与您传递相同的参数调用max（在行话，take不是修改）。

要回答问题的其余部分，您不需要需要的内部帮助函数。

尝试下面的算法转换为斯卡拉：

如果列表为空，抛出一个错误
否则，如果列表中有一个元素返回它的第一个元素
否则
- （递归地）计算最大值m.take(1)，称此为max_of_rest
- 返回更大的m(0)和max_of_rest

有Scala中快乐学习递归！

附录

上述算法，而它产生正确的答案，这样做效率很低。考虑：

maximum([2, 4, 1, 10, 3]) 
    = max(2, maximum([4, 1, 10, 3])) 
    = max(2, max(4, maximum([1, 10, 3]))) 
    = max(2, max(4, max(1, maximum([10, 3])))) 
    = max(2, max(4, max(1, max(10, maximum([3]))))) 
    = max(2, max(4, max(1, max(10, 3)))) 
    = max(2, max(4, max(1, 10))) 
    = max(2, max(4, 10)) 
    = max(2, 10) 
    = 10

请注意每个调用“堆积”在调用堆栈上，消耗大量额外的内存。在这种情况下使用尾递归公式要好得多。

maximum([2, 4, 1, 10, 3]) 
    = _maximum([4, 1, 10, 3], max(4, 2)) 
    = _maximum([1, 10, 3], max(1, 4)) 
    = _maximum([10, 3], max(10, 4)) 
    = _maximum([3], max(3, 10)) 
    = _maximum([], 10) 
    = 10

现在，在这个尾递归的情况下，通过Joost的书房波尔指出，你做有第二功能。你可以看到，这种内在的递归函数是这样的

_maximum(a, v) = 
    if a is empty return v 
    else return _maximum(a.take(1), max(a(0), v))

外部函数是这样

maximum(a) = 
    if a is empty raise an error 
    else return _maximum(a.take(1), a(0))

什么我故意不使用Scala的语法，让您可以享受工作吧。玩的开心！

来源

2017-02-26 19:31:39

很好的答案。然而，为了使解决方案尾递归，你应该总是尝试选择，内部函数是需要恕我直言。 –

哦，你当然是对的！我会将尾递归公式添加到答案中 –

m.take()不修改m。因此，您一次又一次地调用max(m)与同一个数组作为参数。

scala> val m = Array(1, 2, 3, 4, 5); 
m: Array[Int] = Array(1, 2, 3, 4, 5) 

scala> m.take(1) 
res0: Array[Int] = Array(1) 

scala> m 
res1: Array[Int] = Array(1, 2, 3, 4, 5)

还要注意take()没有做所有你认为它在做什么。

scala> m.take(0) 
res2: Array[Int] = Array() 

scala> m.take(3) 
res3: Array[Int] = Array(1, 2, 3)

来源

2017-02-26 19:28:23 avysk

Scala：递归地找到数组的最大值

回答

相关问题