斯卡拉递归

Question

斯卡拉新手，并试图找出递归。

有在我的会议休耕定义：

def inc(n: Int) = n + 1 
def dec(n: Int) = n – 1 

我怎么能重新定义如下函数使用递归INC和DEC？

add(n: Int, m: Int) = n + m 

我有兴趣学习规则递归和尾递归。

感谢

Answer 1

如何：

scala> def inc(n: Int) = n + 1 
inc: (n: Int)Int 

scala> def dec(n: Int) = n - 1 
dec: (n: Int)Int 

scala> def add(n: Int, m: Int): Int = m match { 
    | case 0   => n 
    | case _ if m > 0 => add(inc(n), dec(m)) 
    | case _   => add(dec(n), inc(m)) 
    | } 
add: (n: Int, m: Int)Int 

scala> add(100, 99) 
res0: Int = 199 

scala> add(100, -99) 
res1: Int = 1 

或者还有另一种解决方案，这是Peano axioms的实现。

scala> def add2(n: Int, m: Int): Int = m match { 
    | case 0   => n 
    | case _ if m > 0 => inc(add2(n, dec(m))) 
    | case _   => dec(add2(n, inc(m))) 
    | } 
add2: (n: Int, m: Int)Int 

Answer 2

尾递归有3个部分，据我有关：

• 条件，如果满足条件结束递归
• 返回值，返回值是一个（或源自）尾部递归函数
• 的参数以及条件未满足时的自身调用。

样本：

def inc(n: Int) = n + 1 
def dec(n: Int) = n - 1 


def add(n:Int, m:Int, sum: Int):Int = { 
    //condition to break/end the recursion 
    if (m <= 0) { 
    // returned value once condition is met. This is the final output of the recursion 
    sum 
    } else { 
    //call to itself once condition is unmet 
    add(inc(n), dec(m), n + m) 
    } 
} 

，你可以看到，感觉就像你正在做的，而循环，但功能更强大的方式。

关于递归，调用堆栈的结果是调用堆栈大小作为递归调用的深度（这可能导致stackoverflowexception）在尾递归上它就像while循环被解释的样子。

样本递归：

def addAllNumberFromNToZero(n:Int):Int = { 
    if (m <= 0) { 
    sum 
    } else { 
    n + add(n - 1) 
    } 
} 

Answer 3

使用常规递归，你可以尝试这样的：

def inc(n: Int) = n + 1 
    def dec(n: Int) = n - 1 

    def add(n: Int, m: Int): Int = { 
    if (m == 0) n 
    else add(inc(n), dec(m)) 
    } 

的add的函数递归调用自身add，每次递增n和减少m。当m达到零时，递归停止，此时返回m。