r/PythonLearning • • Aug 16 '25

Recursion is the only way

Post image

This made ne laugh. Why do something without recursion when you can do it with recursion! Actually quite an interesting way to add, or multiply.

44 Upvotes

8 comments sorted by

6

u/Upstairs-Proposal-19 Aug 16 '25

You basically rediscovered Peano arithmetic. In Coq, nat is built from O and S and addition/multiplication are defined by structural recursion, exactly like your code:

Fixpoint add (n m : nat) : nat :=
  match n with
  | O => m
  | S n' => S (add n' m)
  end.

Fixpoint mult (n m : nat) : nat :=
  match n with
  | O => O
  | S n' => add m (mult n' m)
  end.

Why this matters beyond “it runs”:

  • The definitions are total and terminating by construction. Coq enforces that via structural recursion on nat. No hidden edge cases.

  • You can prove properties about them and have a checker verify every step. For example, commutativity of addition is not a test, it is a theorem:

Lemma add_comm : forall n m, add n m = add m n.
Proof.
  induction n as [|n IH]; simpl.
  - (* n = 0 *) reflexivity.
  - (* n = S n *) rewrite IH.
    induction m as [|m IHM]; simpl; [reflexivity| now rewrite IHM].
Qed.

Same idea extends to associativity, distributivity, and everything you expect from arithmetic.

  • Under Curry–Howard, a proof is a program with a type that states the property. So the object you build for add_comm is a value inhabiting the type “addition is commutative,” and Coq checks it like it checks code.

  • You do not need to reprove basics in real projects. The standard library already gives Nat.add_comm, Nat.add_assoc, etc., on top of the Peano nat. Your hand-rolled version is a nice learning step; production proofs usually import the library lemmas.

If you want a gentle path from “this looks like my Python” to “I can prove things about it,” start with the Software Foundations chapters on nat, fixpoints, and induction. They use the same add definition you wrote and build up the proofs from there.

2

u/Mysterious-Man2007 Aug 17 '25

Wow, this is complicated

3

u/Weird-Locksmith3828 Aug 16 '25

run this for negative b

2

u/[deleted] Aug 16 '25

You should have a look at Scheme or OCaml. Both have tail call optimization and are designed to use recursion a lot.

1

u/WhiteHeadbanger Aug 17 '25

If a == 0 then you also have infinite recursion, or is this what should happen?

1

u/Lannok-Sarin Aug 17 '25

That wouldn’t work for negative numbers. They would go on forever.

1

u/pstanton310 Aug 19 '25

Definitely will never overflow the stack