不能理解

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的情況。