使用lambda表达式的递归函数 [英] Recursive function using lambda expression
问题描述
我需要创建一个递归函数重复,该重复函数接受一个函数,并使用x的值对n次使用该函数.这是一个迭代版本,可以更详细地说明我的问题.
I need to create a recursive function repeat which takes in a function and uses the function n number of times with the value of x. Here's an iterative version that explains my issue a bit more in detail.
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. 我该如何使它递归,使其可以像这样工作.
First it takes 3^2, then 3^2^2 which is 81 then again 3^2^2^2 = 6561. How can i make this recursive so it can work like this.
square_three_times = repeat(lambda x: x**2, 3)
print(square_three_times(3)) return 6561
我尝试过类似的操作,但我真的迷失了方向,不知道该怎么办.
I have tried something like this but im really lost and not sure what to do.
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,依此类推.
This obviously wouldnt work since the recursion would keep going forever. But im not sure how i should write this code since i first need to calculate 3^2 before taking the next step 9^2 and so on.
推荐答案
首先,您弄错了基本情况:
First, you've got the base case wrong:
if n == 1:
return fn
毕竟,repeat(fn, 1)
只是一次应用fn
的函数-即fn
.
After all, repeat(fn, 1)
is just a function that applies fn
once—that's fn
.
现在,如果基本情况是n == 1
,则递归情况几乎总是您将n - 1
传递给自己的.
Now, if the base case is when n == 1
, the recursive case is almost always going to be something where you pass n - 1
to yourself.
那么,repeat(fn, n)
和repeat(fn, n-1)
有什么区别?如果您不知道该怎么办,请在您的头上或纸上展开一个简单的盒子:
So, what's the difference between repeat(fn, n)
and repeat(fn, n-1)
? If you can't figure it out, expand a simple case out in your head or on paper:
repeat(fn, 3)(x): fn(fn(fn(x)))
repeat(fn, 2)(x): fn(fn(x))
现在很明显:repeat(fn, n)
与fn(repeat(fn, n-1))
是同一回事,对吗?所以:
And now it's obvious: repeat(fn, n)
is the same thing as fn(repeat(fn, n-1))
, right? So:
else:
def new_fn(x):
return fn(repeat(fn, n-1)(x))
return new_fn
但是,正如电影制片人在评论中指出的那样,在此处使用partial
会更容易:
However, as filmor points out in the comments, it would be easier to use partial
here:
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)
这篇关于使用lambda表达式的递归函数的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!