APT Search – How to Search for Only Installed Packages

Search for packages that are manually installed, and that are a mandatory or recommended dependency of an installed package. Aptitude can do that.

aptitude search -q -F %p '?installed !?automatic (?reverse-depends(?installed .*) | ?reverse-recommends(?installed .*))'

I don't think there's a way to indicate what dependency was found for each package. If you want that information, Python would be the way to go. This very quick-and-dirty script seems to do it (mostly, I think it may be incorrect in some non-straightforward cases involving disjunctions, version dependencies, pre-depends, …).

#!/usr/bin/env python2
import apt
packages = apt.Cache()
covered = {}
# Inverse dependency computation: for each installed package, record which
# packages require it (as Depends: or Recommends:).
for p in packages:
    if p.installed:
        for l in p.installed.dependencies + p.installed.recommends:
            for d in l:
                if packages.has_key(d.name) and packages[d.name].installed:
                    if not covered.has_key(d.name):
                        covered[d.name] = []
                    covered[d.name] += [p.name]
# Print out the manually installed packages that are required by another
# installed package, as well as the requiring package(s).
for p in sorted(covered.keys()):
    if not packages[p].is_auto_installed:
        print(' '.join([p] + covered[p]))

It clearly instructs apt to install & keep recommended packages, but not the suggested packages.

No, it instructs apt to install recommended packages, but not to keep them. You need to specify

APT::AutoRemove::RecommendsImportant "true";

if you want apt to keep recommended packages.