r/PythonLearning • u/RebornCube • Aug 16 '25
Recursion is the only way
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
3
2
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
1
6
u/Upstairs-Proposal-19 Aug 16 '25
You basically rediscovered Peano arithmetic. In Coq,
natis built fromOandSand addition/multiplication are defined by structural recursion, exactly like your code: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:
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_commis 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 Peanonat. 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 sameadddefinition you wrote and build up the proofs from there.