Recursion in C++

1. Fibonacci Sequence

In mathematics, the Fibonacci sequence is a sequence in which each number is the sum of the two preceding ones. Numbers that are part of the Fibonacci sequence are known as Fibonacci numbers, commonly denoted $F_n$. Below is the program to determine a Fibonacci sequence

#include <iostream>
using namespace std;

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

int main(){
    int n;
    cout << "Enter the number of terms: ";
    cin >> n;
    cout << "Fibonacci Series: ";
    for (int i = 0; i < n; i++) {
        cout << fibonacci(i) << " ";
    }
    return 0;
}

Enter the number of terms: 12
Fibonacci Series: 0 1 1 2 3 5 8 13 21 34 55 89

2. Factorial

In mathematics, the factorial of a non-negative integer $n$, denoted by $n!$, is the product of all positive integers less than or equal to $n$. The factorial of $n$ also equals the product of $n$ with the next smaller factorial:

$$ n! = n \times (n - 1) \times (n-2) \times \ldots \times 2 \times 1 = n \times (n-1)!. $$

#include <iostream>
using namespace std;

int nFac(int n) {
    if (n == 0) {
        return 1;
    } else {
        return n * nFac(n - 1);
    }
    // Alternative: for loop
    // for (int i = n - 1; i > 0; i--) {
    //     n *= i;
    // }
    // return n;
}

int main() {
    cout << "Factorial N!" << endl;
    int N;
    cout << "Enter N: ";
    cin >> N;
    cout << N << "! = " << nFac(N) << endl;
    return 0;
}

Factorial N!
Enter N: 5
5! = 120

3. Legendre Polynomials

The Legendre polynomials $P_n(x)$ play an important role in the representation of angular momentum in quantum mechanics (and not only there). Their values obey the recursion formula

$$ (n+1)P_{n+1} (x) = (2n+1) x P_n (x) - n P_{n-1} (x) $$

with the initial conditions $P_0(x) = 0$ and $P_1(x) = x$. A program that outputs the values of all $P_n$ up to $n \leq N$ at the point $x$ is below

#include <iostream>
using namespace std;

double legendre(int n, double x) {
    if (n == 0) {
        return 1;
    } else if (n == 1) {
        return x;
    } else {
        double l = (2.0 * n - 1.0) / n * x * legendre(n - 1, x) 
        - (n - 1.0) / n * legendre(n - 2, x); 
        // Caution: use 2.0 instead of 2 to avoid integer division
        return l; 
    }
}

int main() {
    cout << "Legendre Polynomial" << endl;
    int N;
    cout << "Enter N: ";
    cin >> N;
    cout << "Enter x: ";
    double x_in;
    cin >> x_in;
    for (int i = 0; i <= N; i++) {
        cout << "P" << i << "(" << x_in << ") = " << legendre(i, x_in) << endl;
    } 
    // Alternative: do...while loop
    // do {
    //     cout << "P" << N << "(" << x_in << ") = " << legendre(N, x_in) << endl;
    //     N++;
    // } while (N <= 10);
    return 0;
}

Legendre Polynomial
Enter N: 5
Enter x: 1.2
P0(1.2) = 1
P1(1.2) = 1.2
P2(1.2) = 1.66
P3(1.2) = 2.52
P4(1.2) = 4.047
P5(1.2) = 6.72552

1. Fibonacci Sequence

2. Factorial

3. Legendre Polynomials

Related