2

我正在学习函数式编程语言课程，但在“作为参数的函数”的上下文中我很难理解递归

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，以提高我对 scala（以及函数式编程）的理解，我认为这是一种常见的模式，所以可以提供建议吗？

4

4 回答 4

6

如果n为 0，x则返回。

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

做什么n_times？它采用fwith x、ntimes 或等效调用f的结果：以n_times(f, n - 1, x)(calling f n-1times on x) 的结果调用。

请注意，f我的意思是例如：

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

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

于 2013-01-31T22:53:13.853 回答
4

只需手动扩展。我要打电话n_times nx来节省空间。

核心操作是

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 ) ... ) )
于 2013-01-31T22:54:59.027 回答
3

函数n_times有一个基本案例 whenn = 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
于 2013-01-31T22:57:33.007 回答
0

思考你已经知道的东西是相同的递归，只是混合了另一个概念：高阶函数。

n_times 得到一个函数 (f) 作为参数，因此 n_times 是一个高阶函数，它又能够在他的身体中应用这个 f 函数。实际上这是他的工作，将 fn 次应用于 x。

那么如何将 fn 次应用于 x 呢？好吧，如果你申请了 n-1 次

n_times(f , n - 1 , x)

，然后你再申请一次。

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

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

于 2013-02-01T14:21:05.360 回答