La ricorsione smonta, mentre l'induzione monta.

Esempi su A*. Definire funzioni per ricorsione strutturale

• Funzione concat: A* x A → A*
  • Base: ∀x: A concat(ε, x) = x
  • Passo: ∀ x: A ∀ y: A ∀ p: A* concat(xp, y) = x・concat(p,y)
• Funzione inverse: A* → A*
  • Base: inverse(ε) = ε
  • Passo: ∀ x: A ∀ p: A* inverse(xp) = concat(inverse(p),x)
• Funzione lung: A* → N
  • Base: lung(ε) = 0
  • Passo: ∀ x: A ∀ p: A* lung(xp) = lung(p) + 1