in reply to Re^2: How am i doing?
in thread How am i doing?

> Fibonacci is the schoolbook example for with recursive calls

Are you sure? I'm not sure what you mean exactly because of all the prepositions, but implementing the Fibonacci sequence by recursion is very ineffective inefficient. It's a schoolbook example of memoisation and implementing a recursive formula without recursion, I'd say.

I agree with the rest of your node, though.

Updated: Thanks LanX.

map{substr$_->[0],$_->[1]||0,1}[\*||{},3],[[]],[ref qr-1,-,-1],[{}],[sub{}^*ARGV,3]

Replies are listed 'Best First'.
Re^4: How am i doing?
by LanX (Saint) on Jul 21, 2025 at 10:20 UTC
    ChatGPT agrees, HOW CAN I BE WRONG? ;-P

    Yes, the Fibonacci sequence is a classic example used to illustrate the concept of recursion in computer science and programming. The Fibonacci sequence is defined as follows: - 'F(0) = 0' - 'F(1) = 1' - 'F(n) = F(n-1) + F(n-2) for n > 1' In a recursive implementation, the function calls itself to compute the values of F(n-1) and F(n-2) until it reaches the base cases (F(0) and F(1)). This example effectively demonstrates how recursion works, including the concepts of base cases and recursive cases. However, it's worth noting that while the recursive approach is straightforward, it is not the most efficient way to compute Fibonacci numbers due to its exponential time complexity.

    Yes I'm sure, because I've seen it multiple times used this way, IIRC also in HOP.

    The F(n) = F(n-1) + F(n-2) for n > 1 part is straightforwardly implemented with recursion.

    > implementing the Fibonacci sequence by recursion is very ineffective.

    (Slightly nitpicking) It's inefficient but effective!

    The point is you get a correct result, even if you waste processing power.

    The "memoisation" you mentioned solves this efficiency problem of needlessly recalculating known results.

    IOW, the schoolbook continues evolving the example to deeper depth (sic).

    Keep in mind that the classic MIT lectures on programming used to be in Lisp and original Lisp didn't have loops, only those "tail recursions".

    Cheers Rolf
    (addicted to the Perl Programming Language :)
    see Wikisyntax for the Monastery

[reply]
[d/l]

      Yes, you do recall correctly. From section 1.8 of HOP (page 33 in my version):

      Sometimes a problem appears to be naturally recursive, and then the recursive solution is grossly inefficient. A very simple example arises when you want to compute Fibonacci numbers. This is a rather unrealistic example, but it has the benefit of being very simple.

      🦛

[reply]
        > Keep in mind that the classic MIT lectures on programming used to be in Lisp and original Lisp didn't have loops, only those "tail recursions".

        I know pretty well, and that's not just Lisp. At $job-2, we had a significant codebase in Erlang, which doesn't have loops, either.

        map{substr$_->[0],$_->[1]||0,1}[\*||{},3],[[]],[ref qr-1,-,-1],[{}],[sub{}^*ARGV,3]
[reply]
[d/l]

In Section Seekers of Perl Wisdom