It would've been nice if mathematical induction were indicated as the foundation of recursion. You're not assuming "it does the right thing" and then proving "i

It would've been nice if mathematical induction were indicated as the foundation of recursion. You're not assuming "it does the right thing" and then proving "it does the right thing". What you're doing is that you're proving that "it does the right thing" by showing that "it does the right thing for N" if "it does the right thing for N-1", and your terminal condition is something like "it does the right thing for 0". Thus mathematical induction takes care of both correctness and termination.