Recursive functions in C++: examples

Question

I am starting to learn C++ and I am currently focusing on recursive functions. I’ve seen some interesting examples, like the factorial calculation of a number, but I’d like to see other examples. I hope you will not consider this question too broad. It’s just about seeing and sharing other examples that might be useful to those learning the language. Thank you!

Answer 1

Here’s a program I wrote some time ago to teach functions, in particular to exemplify the difference between normal (using an iterative algorithm) and recursive functions. In this case, it is intended to calculate the values of the Fibonnaci sequence (see here for example).

---

/*
 *       Sequência de Fibonacci  
 *       (de forma normal e de forma recursiva; esta última é bem mais lenta)
 *
 */


#include <iostream>
using namespace std;

unsigned long long fibonacci(const unsigned int n){
    unsigned long long resultado;
    if (n==0)
        resultado=0;
    else if (n==1)
        resultado=1;
        else{
            unsigned long long tabela[n+1];
            tabela[0]=0;
            tabela[1]=1;
            for (auto i=2;i<=n;++i){
                tabela[i]=tabela[i-2]+tabela[i-1];
            }
            resultado=tabela[n];
        }           
    return resultado;
}

unsigned long long fibonacciRecursive(const unsigned int n){
    if (n==0)
        return 0;
    else if (n==1)
         return 1;
        else
            return(fibonacciRecursive(n-2)+fibonacciRecursive(n-1));
}


int main(){
    unsigned int numero;

    do{
        cout << "Escolha numero (0 para terminar): ";
        cin >> numero;
        cout << "O numero de fibonnaci de ordem " << numero << " e " << fibonacci(numero) << endl;
        cout << "O numero de fibonnaci de ordem " << numero << " e " << fibonacciRecursive(numero) << endl;
        cout << endl;
    }while(numero!=0);

    return 0;
}