Algoritmi C/C++

La ricorsione e lo stack delle chiamate in C e C++

In questa lezione calcolerai il fattoriale con una funzione ricorsiva e capirai il caso base e il costo in memoria della ricorsione.

Introduzione

La ricorsione è la tecnica di risolvere un problema riducendolo a un problema più piccolo dello stesso tipo. Ogni funzione ricorsiva ha bisogno di un caso base (base case), e ogni chiamata deve avvicinarsi a esso; altrimenti il programma continua a chiamare la funzione all'infinito.

Punti importanti

Prova con input vuoti, con un solo elemento, con valori ripetuti e già ordinati.
Prima fai funzionare il codice correttamente, poi ottimizza.
Nel codice reale preferisci le funzioni pronte della libreria standard.

Guarda come funziona

Premi Passo per seguire ogni chiamata. Le nuove chiamate finiscono sullo stack delle chiamate e ognuna restituisce il suo valore a chi l'ha fatta.

Esempi di codice C e C++

Esegui →

main.c

#include <stdio.h>

unsigned long long factorial(unsigned number) {
    return number < 2 ? 1 : number * factorial(number - 1);
}

int main(void) {
    printf("%llu\n", factorial(6));
}

Risultato dell'esecuzione

C++

Esegui →

main.cpp

#include <iostream>

constexpr unsigned long long factorial(unsigned number) {
    return number < 2 ? 1 : number * factorial(number - 1);
}

int main() {
    constexpr auto value = factorial(6);
    std::cout << value << '\n';
}

Risultato dell'esecuzione

Confronto tra C e C++

La funzione factorial restituisce 1 quando number è minore di 2, che è il caso base; altrimenti restituisce number * factorial(number - 1). Ogni chiamata occupa un altro pezzo di memoria nello stack delle chiamate (call stack), quindi l'algoritmo usa tempo O(n) e O(n) di stack. La versione in C++ marca la funzione come constexpr, così il valore si può calcolare già in fase di compilazione. Con input grandi conviene controllare i dati e di solito usare un ciclo al posto della ricorsione.

Cicli, puntatori, lunghezze e buffer temporanei sono scritti esplicitamente.

C++

Iteratori e algoritmi standard separano l'elaborazione dal modo in cui i dati sono memorizzati.

Esercizi di approfondimento

Esegui entrambe le versioni e poi modifica il codice per osservare la differenza di sicurezza che offre ciascun linguaggio.

Simula ogni confronto su carta.
Prova con valori ripetuti e con valori molto grandi e molto piccoli.
Misura il tempo del tuo codice e confrontalo con la libreria standard.

Esercitati con una sfida

Usa ciò che questa lezione spiega per risolvere un problema reale. Ogni sfida gira nel browser, con test immediati e una revisione dell'IA.

Tutte le sfide