How not to teach recursion (2021)

I don't know if that's a helpful framing?

    def sum(arr):
       total = 0
       for x in arr:
          total += x
       return total

and

    def sum(arr):
      if len(arr) == 0:
         return 0
      return arr[0] + sum(arr[1:])

both operate over an array but I'd call one of them recursive and the other iterative.

I agree with the overall sentiment. I taught for awhile and was happy with the approach I came up with. Students start out with the basics of learning how to loop through a list to transform some data. Once they have looping down, they are introduced to map and other built in methods. But, before using these methods, they are tasked with rewriting them using the looping they've learned.

Once they've "earned" the usage of the built in methods, they are tasked with rewriting them again, but this time without using any kind of looping. I give them a bit of time to think about how they may do this. Very few students get it but the plan is to live code it myself as an introduction to recursion. The task is still the same: to rewrite the map method. So the context for their intro to recursion is something they've become quite familiar with. It seems to have worked well.

Do people talk about "inductive definitions"? I mostly only hear about induction in the context of proofs, in which case I'd say that an inductive proof/argument is one that uses the recursive structure of whatever it's about.

A recursive definition is: "natural numbers are 0 or a natural number + 1". An (abridged) inductive proof that uses the recursive nature of natural numbers: "the sum of all naturals up to n is n(n+1)/2: 0*(0+1)/2 = 0, and (n+1) + n(n+1)/2 = (2(n+1) + n(n+1))/2 = (2n + 2 + n^2 + n)/2 = (n^2 + 3n + 2)/2 = (n+1)(n+2)/2 = (n+1)((n+1)+1)/2"

They don’t mention “divide and conquer” at all, which I find a pretty compelling use of recursion even for non-inherently recursive problems. Writing a merge sort recursively is much easier and clearer than the nonrecursive variant.