An introduction to lockless algorithms [LWN.net]

An introduction to lockless algorithms

Posted Feb 21, 2021 12:29 UTC (Sun) by Wol (subscriber, #4433)
In reply to: An introduction to lockless algorithms by pebolle
Parent article: An introduction to lockless algorithms

int fibonacci( int f)
{
if (f <= 1)
return f;
else
return fibonacci( f-1) + fibonacci( f-2);
}

Which will blow your stack for large values of f :-)

I hope I've got it right ... :-)

Cheers,
Wol

Posted Feb 21, 2021 15:24 UTC (Sun) by Wol (subscriber, #4433) [Link] (1 responses)

I knew I should have checked it ...

The start of the conditional should be

if (f <= 2) return 1;

Cheers,
Wol

Posted Feb 21, 2021 16:16 UTC (Sun) by yann.morin.1998 (guest, #54333) [Link]

> The start of the conditional should be
> if (f <= 2) return 1;

Not necessarily. The generalised Fibonacci sequence starts with F(0) = 0 and F(1) = 1 [0]. So your initial condition was (not in)correct.

Posted Feb 21, 2021 17:10 UTC (Sun) by matthias (subscriber, #94967) [Link]

This will definitely not blow the stack. Even for quite small numbers of f, the runtime will be longer than the age of the universe.

Posted Feb 21, 2021 23:41 UTC (Sun) by neilbrown (subscriber, #359) [Link]

> Which will blow your stack for large values of f :-)

Only if you try to implement it on a computer.
As a mathematical abstraction, this is perfectly fine and well defined for all f.

Posted Mar 5, 2021 0:13 UTC (Fri) by qzPhUZ7af5M6kjJi3tDgMaVq (guest, #140267) [Link]

Recursive definitions work just fine in certain programming languages.

In a Haskell interpreter:

Prelude> let fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
Prelude> fibs !! 100000

(20,899 digit number omitted... it took about 2 seconds to compute it)