Se la dipendenza è una raccomandazione, aptitude cerca di capire se è una «nuova» raccomandazione o una raccomandazione «precedentemente soddisfatta». aptitude considera una raccomandazione come «nuova» se il pacchetto che la dichiara non è attualmente installato oppure se la sua versione installata non raccomanda un pacchetto con lo stesso nome. Al contrario, una raccomandazione è «precedentemente soddisfatta» se il pacchetto che la dichiara è installato, la versione attualmente installata raccomanda un pacchetto con lo stesso nome e tale raccomandazione è soddisfatta.

Per esempio, si supponga che la versione 1.0 di prog raccomandi la versione 4.0 di bellalib1, ma che la versione 2.0 di prog raccomandi la versione 5.0 di bellalib1 e raccomandi inoltre apache. Se si scegliesse di aggiornare prog dalla versione 1.0 alla versione 2.0, la raccomandazione di apache verrebbe considerata «nuova» perché la versione 1.0 di prog non raccomandava apache. Al contrario, la raccomandazione di bellalib1 non sarebbe «nuova», perché la versione 1.0 di prog raccomandava bellalib1, anche se raccomandava una versione diversa. In ogni caso, se bellalib1 fosse già installata, allora tale raccomandazione verrebbe considerata «precedentemente soddisfatta».

Se l'opzione di configurazione APT::Install-Recommends è impostata a true, aptitude cerca sempre di soddisfare le raccomandazioni «nuove» e «precedentemente soddisfatte»; tutte le altre vengono ignorate dalla risoluzione immediata. Se quella opzione è impostata a false, la risoluzione immediata delle dipendenze ignora tutte le raccomandazioni.

Se la dipendenza è verso diversi pacchetti combinati con OR, esamina tutte le alternative nell'ordine in cui sono fornite. Per esempio, se un pacchetto dipende da «exim | mail-transport-agent», aptitude prima esamina exim, poi mail-transport-agent.

Per ciascuna alternativa, cerca di risolverla. Se la dipendenza è un conflitto, rimuove l'alternativa attuale se è installata (e per un conflitto non relativo ad una specifica versione, rimuove anche qualsiasi pacchetto che fornisce l'oggetto del conflitto). Altrimenti installa la versione candidata dell'alternativa attuale, se soddisfa la dipendenza. Se ciò non è vero, o se non è presente una versione candidata (ad esempio, perché l'alternativa attuale è un pacchetto virtuale), e se la dipendenza non è relativa ad una specifica versione, cerca di installare il pacchetto con più alta priorità^[12] la cui versione candidata fornisca l'oggetto dell'alternativa attuale.

Per esempio, si supponga di voler risolvere la dipendenza «Dipende: exim | mail-transport-agent». aptitude cercherebbe come prima cosa di installare il pacchetto exim. Se exim non fosse disponibile, aptitude cercherebbe quindi di installare il pacchetto con più alta priorità la cui versione candidata fornisca exim. Se non esistesse un tale pacchetto, aptitude installerebbe il pacchetto con più alta priorità la cui versione candidata fornisca il pacchetto virtuale mail-transport-agent. D'altro canto, supponendo che la dipendenza sia «Dipende: exim (>= 2.0.0) | mail-transport-agent», ma che sia disponibile solo la versione 1.0 di exim, aptitude in questo caso non installerebbe exim (perché la versione non corrisponde), né cercherebbe di installare pacchetti che forniscono exim (perché i pacchettti virtuali non possono soddisfare la corrispondenza con una restrizione sulla versione). aptitude perciò ripiegherebbe sull'installazione del pacchetto con più alta priorità la cui versione candidata fornisca mail-transport-agent.

Se il passo precedente ha installato un pacchetto, risolve le sue dipendenze usando questo algoritmo e poi si ferma.