Re: Recursion




Rob Thorpe wrote:
andy@xxxxxxxxxxxxxxxxxxxxxxxxx wrote:
Rob Thorpe wrote:

[cut example]

Interesting. In CL you would do something like:-

(defun fibonacci (n)
"Compute the N'th Fibonacci number."
(if (or (zerop n) (= n 1))
1
(+ (fibonacci (- n 1)) (fibonacci (- n 2)))))

(eval-when (:compile-toplevel :load-toplevel)
(defvar fib35 (fibonacci 35))

... though I haven't tested this.

I cant say I'm familiar at all with CL. In the above the function is
conditionally calculated at compile-time/run-time dependent on a
predicate somewhere in the last clause?

Yes. The first form beginning "defun fibonacci" defines a function to
calculate fibonacci numbers. Later the call "(fibonacci 35)"
calculates the 35th fibonacci number. The form "eval-when" tells the
compiler to evaluate what follows at compile time (or load time) rather
than run-time.

To me it sounds weird that you wouldnt just say calculate whatever you
can at compile time ( Thats what much optimisation amounts to after
all), unless CL is interpreted of course. I'm guessing CL must be a
so-called functional language?

I thought that your code calculated the 35th fibonacci number that's
what mine does. I see now that yours calculates all numbers up to 35.

It does but at compile time rather than runtime.Its an O(1) fibonacci
function.

[...]

I could make MAX_FIB bigger when I detect these platforms without
danger of overflow. In another scenario the MAX_FIB #define could be
placed in a 'config' header file so that the user can control (for
example) the array length, his-or-herself.

I see, it makes it flexible against future changes.

I would still be tempted if writing C to put the task in a small
program and call it from a line in the makefile, using command
arguments to pass on parameters such as the number of fib numbers. I
can see the benefits of doing it this way though.

Much C++ library code exists as headers only ( Especially code
involving C++ templates for example, which must have the source
available to be able to instantiate the template) and is easiest
compiled on the fly with various configs options, rather than being
stored as object code, which is pretty well fixed, so I would think it
would be impractical to prefer the use of a makefile over Macros.

If the values computed in the array initialiser list had been
pre-computed externally then obviously this type of versatility would
not be available, so it is extremely advantageous to be able to do
things this way. ( OTOH The Wave C/C++ preprocessor also from
http://www.boost.org does provide a mechanism to call external code
generators FWIW)

The C++ preprocessor is a tortuous beast and I sincerely admire Paul
Mensonides for providing the Boost Preprocessor library which provides
something more similar to a traditional language with math and looping
constructs as I hope can be recognised in the above macros.

I can understand some of it, but I can't understand it properly. I'm
not familar with complex uses of the preprocessor like this one.

To be honest I dont understand the Boost.Preprocessor library very well
myself. I just copy paste the required functionality as necessary. For
example the above BOOST_PP_REPEAT is described in

http://boost-consulting.com/tmpbook/preprocessor.html

The documentation for the Boost.Preprocessor library is also available:

http://www.boost.org/libs/preprocessor/doc/index.html

regards
Andy Little

.



Relevant Pages

  • Re: Recursion
    ... "Compute the N'th Fibonacci number." ... The first form beginning "defun fibonacci" defines a function to ... The C++ preprocessor is a tortuous beast and I sincerely admire Paul ...
    (comp.programming)
  • Re: Recursion
    ... "Compute the N'th Fibonacci number." ... The first form beginning "defun fibonacci" defines a function to ... compiler to evaluate what follows at compile time rather ... would be impractical to prefer the use of a makefile over Macros. ...
    (comp.programming)
  • Re: Recursion
    ... Of course the input for the compile time fibonacci must be known at ... static const int value ... struct fibonacci{ ...
    (comp.programming)
  • Re: How useful is "trace"
    ... almost never tells me clearly how the function i'm tracing is really ... (defun fibonacci (n) ... (trace fibonacci) ...
    (comp.lang.lisp)
  • Re: How useful is "trace"
    ... (defun fibonacci (n) ... (trace fibonacci) ...  ;;ecl or sbcl ...
    (comp.lang.lisp)