nixin72 nixin72 - 3 years ago 123
Python Question

Print the first n numbers of the fibonacci sequence in one expression

So I've been messing around with Python a bit lately and I'm trying to find a way to output the nth number of the fibonacci sequence in a single expression. This is the code that I've written so far:

(lambda f: f if f<2 else (f-1)+(f-2))(n)
# n == 1 -> 1
# n == 2 -> 1
# n == 3 -> 3
# n == 4 -> 5
# n == 5 -> 7

However, as I commented above this simply outputs a set of odd numbers. I'm confused as to why this is happening because if I am to re-write this as a named lambda function, it would look something like this:

f = lambda n: n if n<2 else f(f-1)+f(f-2)
# f(1) -> 1
# f(2) -> 1
# f(3) -> 2
# f(4) -> 3
# f(10) -> 55

Now the reason I've added the Lambda Calculus tag is because I'm not sure if this question falls under the domain of simply understanding how Python handles this. I've read a tiny bit about the Y combinator in lambda calculus, but that's a foreign language to me and couldn't derive anything from resources I found for this about lambda calculus.

Now, the reason I'm trying to do this in one line of code, as opposed to naming it, is because I want to try and put this lambda function into list comprehension. So do something like this:

[(lambda f: f if f<2 else (f-1)+(f-2))(n) for n in range(10)]

and create an array of the first x numbers in the fibonacci sequence.

What I'm looking for is a method of doing this whole thing in one expression, and should this fall under the domain of Lambda calculus, which I believe it does, for someone to explain how this would work.

Feel free to offer an answer in JavaScript, C#, or other C-like languages that support Lambda functions.

EDIT: I've found the solution to what I was attempting to do:

[(lambda f: (lambda x: f(lambda v: x(x)(v)))(lambda x: f(lambda v: x(x)(v))))(lambda f:(lambda n: n if n<2 else f(n-1)+f(n-2)))(y) for y in range(10)]

I know that this is not at all practical and this method should never be used, but I was concerned with CAN I do this as opposed to SHOULD I ever do this.

Answer Source

You have to somehow assign a name to it in order to use a recursive definition--otherwise a recursive lambda function is impossible in Python since it doesn't have any special reflexive keyword that refers to it.

As TerryA mentioned, you could use the trick in this post in order to generate a sequence of x Fibonacci numbers in one statement with the recursive definition.

Or, you could use the closed form, which would be much faster:

[int(round((lambda n: ((1+5**0.5)**n-(1-5**0.5)**n)/(2**n*5**0.5))(x)))
 for x in range(10)]

This assumes that x is not very large, though, because the float arithmetic will overflow around x=600 and will probably have large rounding errors before that point.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download