fibonacci series what Iam is missing ?

[Rustom Mody]

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;
};