使用lambda表達式的遞歸函數

Question

我需要創建一個遞歸函數repeat，它接受一個函數，並使用該函數的n次值與x的值。這裏有一個迭代版本，詳細解釋了我的問題。

def repeat(fn, n, x): 
    res = x 
    for i in range(n): 
     res = fn(res) 
     print(res) 
    return res 

print(repeat(lambda x: x**2, 3, 3)) returns 6561 

首先需要3^2，然後是3^2^2是81話又說回來3^2^2^2 = 6561. 我怎樣才能使這個遞歸，因此它可以像這樣工作。

square_three_times = repeat(lambda x: x**2, 3) 
print(square_three_times(3)) return 6561 

我試過類似的東西，但我真的失去了，不知道該怎麼做。

def repeat(fn, n): 
    if n == 1: 
     return fn(n): 
    else: 
     def result(x): 
      return fn(n) 
    return repeat(fn,result(x)) 

這顯然不會工作，因爲遞歸會一直持續下去。但我不知道我該怎麼寫這個代碼，因爲我需要在進行下一步9^2之前先計算3^2等等。

Answer 1

首先，你已經得到了基本情況不對：

if n == 1: 
    return fn 

畢竟，repeat(fn, 1)僅僅是一次適用fn是fn功能。

現在，如果基本情況是當n == 1，遞歸情況幾乎總是會通過n - 1給你自己。

那麼，repeat(fn, n)和repeat(fn, n-1)有什麼區別？如果你不能弄清楚，展開一個簡單的情況下，出在你的頭上或在紙上：

repeat(fn, 3)(x): fn(fn(fn(x))) 
repeat(fn, 2)(x): fn(fn(x)) 

而現在很明顯：repeat(fn, n)是一回事fn(repeat(fn, n-1))，對不對？所以：

else: 
    def new_fn(x): 
     return fn(repeat(fn, n-1)(x)) 
    return new_fn 

---

然而，隨着filmor在評論中指出，這將是更容易在這裏使用partial：

def repeat3(fn, n, x): 
    if n == 1: 
     return fn(x) 
    else: 
     return fn(repeat3(fn, n-1, x)) 

def repeat(fn, n): 
    return functools.partial(repeat3, fn, n) 

Answer 2

您可以在舊的重複方面非常簡單地定義這個功能：

repeat_new = lambda fn, n: lambda x: repeat(fn, n, x) 

square_three_times = repeat_new (lambda x: x**2, 3) 
print(square_three_times(3))