不能理解

Question

我采取了函数式编程语言当然，我有困难“作为参数的函数”

fun n_times(f , n , x) = 
    if n=0 
    then x 
    else f (n_times(f , n - 1 , x)) 

fun double x = x+x; 

val x1 = n_times(double , 4 , 7); 

the value of x1 = 112 

的上下文中理解递归“功能参数”递归这加倍“X”' N”倍，以便7一倍4倍= 112

我可以理解简单的递归模式，如在一个列表中，或添加号码‘的力量’的功能，但我不理解此功能如何‘通过调用本身n_times’求值？可以提供该功能如何工作的解释？

我已经标记使用Scala为我修这门课程来提高我的斯卡拉的理解（连同函数式编程），我认为这是一个常见的模式，可能可以提供意见？

Answer 1

功能n_times具有基部情况下n = 0否则感应的情况。您在归纳案例中递归，直到终止基本案例。

这里是一个说明性的痕迹：

n_times(double, 4, 7) 
~> double (n_times(double, 3, 7)) (* n = 4 > 0, inductive case *) 
~> double (double (n_times(double, 2, 7))) (* n = 3 > 0, inductive case *) 
~> double (double (double (n_times(double, 1, 7)))) (* n = 2 > 0, inductive case *) 
~> double (double (double (double (n_times(double, 0, 7))))) (* n = 1 > 0, inductive case *) 
~> double (double (double (double 7))) (* n = 0, base case *) 
~> double (double (double 14)) 
~> double (double 28) 
~> double 56 
~> 112 

Answer 2

如果n为0，x返回。

否则，返回f (n_times(f , n - 1 , x))。

n_times是做什么用的？需要拨打fx,n次，或等效拨打电话f，结果为（致电fn-1次x）。

注意通过调用f我的意思，例如：

调用f 3次：f(f(f(x)))

调用f 2次：f(f(x))

Answer 3

只需用手扩大。我打算拨打n_timesnx以节省空间。

核心操作是

nx(f, n, x) -> f(nx(f, n-1, x)) 

与

nx(f, 0, x) -> x 

所以终止，当然，

nx(f, 1, x) -> f(nx(f, 0, x)) -> f(x) 
nx(f, 2, x) -> f(nx(f, 1, x)) -> f(f(x)) 
... 
nx(f, n, x) -> f(nx(f,n-1,x)) -> f(f(... f(x) ...)) 

Answer 4

这是相同的递归想你已经知道了，只是另一个概念混合高阶函数。

n_times得到一个函数（f）作为一个参数，所以n_times是一个高阶函数，这又能够在他的身体来应用此f函数。实际上，这是他的工作，将f n次应用于x。

那么如何将f n次应用到x？那么，如果你申请n-1次

n_times(f , n - 1 , x) 

，那么你再申请一次。

f (n_times(f , n - 1 , x)) 

像往常一样，您必须停止递归，即x = n = 0的情况。