On Tue, 24 Mar 2015 11:59 am, Chris Angelico wrote:
> I've never thought of the mathematical definition as being inherently > recursive; but as inherently sequential. Sure, you can define counting > numbers based on sets (0 is the cardinality of the empty set, 1 is the > cardinality of the set containing the empty set, et-set-era), but most > people will define them by counting. The Fibonacci sequence is > logically defined by starting somewhere and then adding to the > sequence. Yes, you can define it recursively too, but it's just as > easy to define it as a progression. But what are you adding? You're not adding a constant or simple expression each time, but a previous term of the series. That's recursion. The mathematical term is that it is a recurrence relation, and is usually written: F[n] = F[n-1] + F[n-2] where F[x] means F subscript x. In English: the nth Fibonacci number is equal to the sum of the previous two Fibonacci numbers (with the first and second given by 0 and 1 respectively). That's inherently recursive: the definition is given in terms of itself. http://en.wikipedia.org/wiki/Fibonacci_number There is at least one closed-form (non-recursive) formula for Fibonacci numbers, Binet's Formula: F[n] = (φ**n - ψ**n)/sqrt(5) where: φ is the Golden Ratio (1+sqrt(5))/2 ψ = 1-φ but that's not how the Fibonacci numbers are defined, or why they are interesting. The Fibonacci numbers are just a special case for a more mathematically interesting family of recurrence relations, the Lucas sequences. (Aside: due to floating point rounding, Binet's Formula will give inaccurate results for large enough values of n. With n=77 it is off by 1.) The important thing here is that all these associated sequences -- Fibonacci numbers, Pell numbers, Leonardo numbers, Perrin numbers and others -- are defined as recurrences, i.e. recursively. But that doesn't necessarily make recursion the best way to implement it. -- Steven -- https://mail.python.org/mailman/listinfo/python-list
