On Tuesday, March 24, 2015 at 7:22:25 AM UTC+5:30, Steven D'Aprano wrote: > 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.
I think (guess) Chris is saying that recurrence relations are somehow 'less recursive' than recursion? I find that view weird... though I should admit to making a similar one: Recursion is not hard; its recursion mixed with imperative programming that's a mismatch and therefore seems hard: http://blog.languager.org/2012/10/functional-programming-lost-booty.html The other unsatisfactory aspect of above discussion is that it seems to assume recursion = recursive function What about recursive data? eg the C list definition: ?? struct node { int elem; struct node *next; }; In fact that's not just recursive its mutually recursive. Becomes evident if rewritten as typedef struct node *nodeptr; struct node { int elem; nodeptr next; }; -- https://mail.python.org/mailman/listinfo/python-list
