Recursive functions in C++: examples

I'm starting learning in C++ and, for the moment, I'm focusing on recursive functions. I've seen some interesting examples, like calculating the factorial of a number, but I'd like to see other examples. I hope you do not consider this question too broad. It's just about seeing and sharing other examples that can be useful to those who are learning the language. Thank you!

Author: Alexandre Cartaxo, 2015-12-11
Source

1 answers

Here is a program I wrote some time ago with the aim of teaching functions, in particular exemplifying the difference between normal (using an iterative algorithm) and recursive functions. In this case, we intend to calculate the Fibonnaci sequence values (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;
}
 1
Author: Alexandre Cartaxo, 2015-12-11 06:01:27