namespace tf {

/** @page ExamplesFibonacciNumber Fibonacci Number

We study recursive task parallelism using the Fibonacci sequence as a
concrete example, demonstrating how tf::Runtime enables dynamic task
creation and cooperative synchronisation without blocking worker threads.

@tableofcontents

@section FibonacciNumberProblem Problem Formulation

The Fibonacci sequence is defined such that each number is the sum of the
two preceding ones, starting from 0 and 1:

<tt>0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...</tt>

The natural recursive implementation is:

@code{.cpp}
int fibonacci(int n) {
  if(n < 2) return n;
  return fibonacci(n-1) + fibonacci(n-2);
}
@endcode

The two recursive calls are mutually independent and can therefore run in
parallel.
The challenge is to express this recursive parallelism efficiently —
spawning tasks that themselves spawn tasks — without blocking worker
threads or creating unbounded overhead.

@section RecursiveFibonacciParallelismUsingRuntimeTasking Recursive Fibonacci with Runtime Tasking

A runtime task accepts a tf::Runtime& parameter, giving it a live handle
to the scheduling runtime.
We use tf::Runtime::silent_async to spawn both recursive branches in
parallel and tf::Runtime::corun to wait for them cooperatively.
@c corun does not block the calling worker — it participates in the
work-stealing loop while waiting, so other tasks can run on the same
thread:

@code{.cpp}
#include <taskflow/taskflow.hpp>

size_t fibonacci(size_t N, tf::Runtime& rt) {

  if(N < 2) return N;

  size_t res1, res2;

  // spawn both branches as async runtime tasks
  rt.silent_async([N, &res1](tf::Runtime& rt1) {
    res1 = fibonacci(N-1, rt1);
  });
  rt.silent_async([N, &res2](tf::Runtime& rt2) {
    res2 = fibonacci(N-2, rt2);
  });

  // cooperatively wait for both branches without blocking the worker
  rt.corun();

  return res1 + res2;
}

int main() {

  tf::Executor executor;

  size_t N = 30, res;
  executor.silent_async([N, &res](tf::Runtime& rt) {
    res = fibonacci(N, rt);
  });
  executor.wait_for_all();

  std::cout << N << "-th Fibonacci number is " << res << '\n';

  return 0;
}
@endcode

Each call to @c fibonacci recursively spawns two async tasks and then
waits cooperatively for both to finish.
The executor distributes tasks across all available workers using
work-stealing, achieving parallelism at every level of the recursion tree.
The execution diagram for @c fibonacci(4) is shown below.
The suffixes @em _1 and @em _2 denote the left and right children spawned
by their parent runtime:

@dotfile images/fibonacci_4.dot

@subsection TailRecursionOptimization Tail Recursion Optimisation

Spawning both branches asynchronously doubles the number of async tasks
created: one branch is always available for inline computation in the
current execution context, so spawning it asynchronously only adds
scheduling overhead without increasing parallelism.
The standard optimisation is to compute one branch @em inline (directly in
the current context) and spawn only the other asynchronously.
This halves the task count, reduces stack pressure, and cuts scheduling
overhead at every level of recursion:

@code{.cpp}
size_t fibonacci(size_t N, tf::Runtime& rt) {

  if(N < 2) return N;

  size_t res1, res2;

  // spawn only the left branch asynchronously
  rt.silent_async([N, &res1](tf::Runtime& rt1) {
    res1 = fibonacci(N-1, rt1);
  });

  // compute the right branch inline in the current context
  res2 = fibonacci(N-2, rt);

  // cooperatively wait for the left branch
  rt.corun();

  return res1 + res2;
}
@endcode

The optimised execution diagram for @c fibonacci(4) is shown below.
The right branch at each level has been eliminated, replaced by inline
computation:

@dotfile images/fibonacci_4_tail_optimized.dot

@subsection FibonacciNumberBenchmarking Benchmarking

The table below compares wall-clock runtime of the two implementations
across different values of @c N on a multi-core machine:

<div align="center">
| N   | with tail optimisation | without tail optimisation |
| :-: | :-:                    | :-:                       |
| 20  | 0.23 ms                | 0.31 ms                   |
| 25  | 2 ms                   | 4 ms                      |
| 30  | 23 ms                  | 42 ms                     |
| 35  | 269 ms                 | 483 ms                    |
| 40  | 3003 ms                | 5124 ms                   |
</div>

The performance gap widens as @c N increases because the number of tasks
created grows exponentially.
At @c N = 40, tail optimisation cuts runtime by over 40% by eliminating
half the task-creation and scheduling overhead at every recursive level.

@section RecursiveFibonacciParallelismUsingTaskGroup Recursive Fibonacci with Task Group

tf::TaskGroup offers a lighter-weight alternative to tf::Runtime for
recursive parallelism from any calling context — no need for the caller
itself to be a runtime task.
The interface is the same: spawn sub-tasks with @c silent_async, then call
@c corun to wait cooperatively.

@code{.cpp}
tf::Executor executor;

std::function<size_t(size_t)> fibonacci = [&](size_t N) -> size_t {
  if(N < 2) return N;

  size_t res1, res2;
  tf::TaskGroup tg = executor.task_group();

  // spawn left branch; compute right branch inline (tail optimisation)
  tg.silent_async([N, &res1, &fibonacci]() {
    res1 = fibonacci(N-1);
  });
  res2 = fibonacci(N-2);

  tg.corun();   // cooperatively wait for the left branch
  return res1 + res2;
};

int main() {
  size_t N = 30;
  size_t res = executor.async([&]() { return fibonacci(N); }).get();
  std::cout << N << "-th Fibonacci number is " << res << '\n';
  return 0;
}
@endcode

@note
Prefer tf::Runtime when you are already inside a runtime task, as it
avoids the construction overhead of a task group object.
Use tf::TaskGroup when the recursive function is called from a context
that does not hold a tf::Runtime reference.

*/

}
