De un algoritmo se piden tres cosas y la primera es la que se olvida. Terminación: que el ciclo o la recursión alcancen un final para toda entrada válida. Correctitud: que la salida cumpla la postcondición, y para eso sirve la invariante. Costo: tiempo y memoria, diciendo respecto de qué es n. Con el segundo algoritmo de arriba las tres salen cortas: termina porque el ciclo recorre un arreglo finito; es correcto porque al llegar a cada valor, el conjunto contiene exactamente los anteriores; y es lineal en tiempo y en memoria.
Una función recursiva se diseña, no se sigue. Escribí el contrato, resolvé el caso más chico sin llamar a nadie, y achicá el problema confiando en que el contrato vale para la entrada menor. Para convencerte de que termina, buscá una medida que baje; para convencerte de que es correcta, hacé inducción sobre esa medida.
Así te lo toman
En los finales piden justificar que una función recursiva es correcta y termina. La estructura es siempre la misma: una medida que decrece para la terminación, e inducción sobre esa medida para la corrección. Abajo está la demostración completa para total.
La pila de llamadas es la memoria de todo lo que quedó pendiente. Cada invocación apila un marco con sus variables y a dónde volver; cada retorno lo saca. De ahí salen el orden inverso de los resultados, el espacio de una recursión (la profundidad, no la cantidad de llamadas), la forma de leer un stack trace y el límite que convierte un algoritmo correcto en un crash.
Así te lo toman
En los parciales es muy común pedir la traza de una recursión doble —Fibonacci, torres de Hanoi— y preguntar por separado cuántas llamadas se hacen y cuánta memoria se usa. Dibujá el árbol de llamadas para contar el tiempo, y marcá su rama más larga para el espacio.
Recursión e iteración son dos lugares distintos para guardar trabajo pendiente. La recursión lo deja en la pila de llamadas, que es cómoda pero tiene un límite que pone el runtime; el ciclo lo guarda en variables y estructuras que controlás vos. Usá la forma que haga evidente la estructura del problema sin perder el control de la profundidad.
atlas.matiascaliz.com.ar/materias/programacion — si algo de acá no se entiende solo, el post completo lo explica.