Grade 10 · RecursionCitește în română

Recursive Fibonacci

Original: Fibonacci recursiv

ExponentialC++1742 lines2 examples

The idea

The Fibonacci sequence: F(0) = 0, F(1) = 1, F(n) = F(n - 1) + F(n - 2). The direct translation has two recursive calls, so the call tree almost doubles at every level and the same values are recomputed many times (F(3) appears several times in the tree of F(6)). The number of calls, printed next to the result, is 2 * F(n + 1) - 1. The iterative version or memoization solve the problem in O(n).

Original description (Romanian)

Șirul lui Fibonacci: F(0) = 0, F(1) = 1, F(n) = F(n - 1) + F(n - 2). Transcrierea directă are două autoapeluri, deci arborele apelurilor se dublează aproape la fiecare nivel, iar aceleași valori se recalculează de multe ori (F(3) apare de mai multe ori în arborele lui F(6)). Numărul de apeluri, afișat lângă rezultat, este 2 * F(n + 1) - 1. Varianta iterativă sau memorarea valorilor rezolvă problema în O(n).

Complexity
O(φ^n) calls, φ ≈ 1.618 (exponential)
Grade
Grade 10 (Clasa a X-a)
Chapter
Recursion

Examples

Example 1

Input

10

Expected output

55 177
Example 2

Input

1

Expected output

1 1

The code

Comments are in Romanian, as in the original collection. Edit freely: you can reset at any time.

fibonacci-recursiv.cpp
/*
 * Titlu: Fibonacci recursiv
 * Clasa: 10
 * Capitol: Recursivitate
 * Descriere: Șirul lui Fibonacci: F(0) = 0, F(1) = 1, F(n) = F(n - 1) + F(n - 2).
 *            Transcrierea directă are două autoapeluri, deci arborele apelurilor se
 *            dublează aproape la fiecare nivel, iar aceleași valori se recalculează
 *            de multe ori (F(3) apare de mai multe ori în arborele lui F(6)).
 *            Numărul de apeluri, afișat lângă rezultat, este 2 * F(n + 1) - 1.
 *            Varianta iterativă sau memorarea valorilor rezolvă problema în O(n).
 * Complexitate: O(φ^n) apeluri, φ ≈ 1.618 (exponențial)
 *
 * Exemplu
 * Intrare: 10
 * Ieșire: 55 177
 *
 * Exemplu
 * Intrare: 1
 * Ieșire: 1 1
 */
#include <iostream>
using namespace std;

long long apeluri;

long long fib(int n)
{
    apeluri++;
    if (n <= 1)
        return n;
    return fib(n - 1) + fib(n - 2);
}

int main()
{
    int n;
    cin >> n;
    long long f = fib(n);
    cout << f << ' ' << apeluri << '\n';
    return 0;
}

Runs on a real g++ (C++17, -O2) through Compiler Explorer. Keep runs short; there's a time limit.