<!-- language-all: lang-none -->
# Is Recursion hard?
[Peter Deutsch](https://en.wikipedia.org/wiki/L._Peter_Deutsch), the creator of the smalltalk implementation that inspired the java-Jit (and much else), famously said:

> To iterate is human, to recurse divine

So you and your struggling students are in august company!

Now let's turn over to math. And not just math but...
# Basic school math
Here are two identities 
$$a(b+c) = ab + ac \tag{distrib. law}$$
$$x^{m+n} = x^m x^n \tag{index law}$$

I guess everyone will agree that *in the context of school math* these are
unproblematic? Almost trivial?

Lets special-case the above with $c=1$ in the first and $n=1$ in the second and we get
$$a(b+1) = ab + a $$
$$x^{m+1} = xx^m$$

Lets now ponder...

- Are these equations in any way difficult?
- Do you (anyone) find it an issue that they are recursive?
- Does one even **notice** that they are recursive?

(Assuming that the answer to all the above is no,no,no)   x	
Lets ask now:   
Whats this to do with programming?

Well... All we need are base cases, respectively
$$a.0 = 0$$
$$x^0 = 1$$

And we get a complete recursive specification for multiplication as repeated addition and exponentiation as repeated multiplication

These can be trivially<sup>1</sup> translated to haskell

as

    a*(b+1) = a*b + a
    a*0     = 0


and

    x^(m+1) = x*(x^m)
    x^0     = 1

# Returning to the Programming world
Ok so you say that this is some math-toy. What's it to do with programming?
# An inappropriate pun
In almost all today's programming languages you can write the "statement"
`i = 1`

And in math we write $i = 1$

Doing the first makes the second true; or staying in the programming world, after `i = 1`
`i == 1`
becomes true

So what's the big deal?
Well programmers also write
`i = i+1`

(Or moral equivalents like `i++` `i += 1` etc)

So after `i=i+1` does `i == i+1` ?!

Lets ask our math-respecting executor Haskell:  
Ok one can write

     i = i+1
when we ask what is `x` we get

     ? i
     
     ERROR: Control stack overflow

In effect our executor is saying that it got into trouble trying to "solve the equation" $i=i+1$
# So is the problem in programming or math??
**Mathematicians** would almost universally protest at $i=i+1$ as

- wrong
- impossible
- no (finite) solution
- or just plain nonsense
- etc

Clearly if we **programmers** accept `i=i+1` as normal and ok we cannot then expect our **programs** to respect **mathematical** concepts.

So it seems we have
# An inevitable dilemma: Programming XOR Mathematics
This seems like a very high price to pay!

But there's good news!

A large number of very intelligent people for many decades have thought about the problem and come to a very simple conclusion:
# The culprit is assignment
- Once you have assignment, a mathematical semantics of our programming language is a lost cause
- Throw the assignment out of the programming language (and morally equivalent things like mutating data-structures)<sup>2</sup> and your programming language essentially becomes mathematics

# A bit of terminology
- Those who think as above and prefer assignment-free<sup>3</sup> languages are typically called *functional programmers*
- Languages with assignment are called *imperative languages* (and from the pov above OO and classic imperative languages are much the same)

# Conclusion
So in answer to your explicit statement: *My students find recursion hard!* and its implied questions: *Am I or my students doing something wrong?*

The answer is Yes: Using imperative programming in a first programming course
<sup>4</sup> befuddles their thinking

Or hear [Dijkstra's take](https://www.cs.utexas.edu/users/EWD/OtherDocs/To%20the%20Budget%20Council%20concerning%20Haskell.pdf) on this

-------

<sup>1</sup> Ok for those who try this in haskell there are some wrinkles -- Ive tested in [gofer](
https://en.m.wikipedia.org/wiki/Gofer_(programming_language))
  -- **GO**od **F**or **E**quational **R**easoning -- a Haskell predecessor which facilitates this kind of playing around better than Haskell

<sup>2</sup>mutation is actually much worse than assignment; in fact mutation messes up imperative programming as much as imperative programming messes up mathematics. A [brief trailer](https://cseducators.stackexchange.com/a/6567/8837)

<sup>3</sup> And sequencing... A story for another day

<sup>4</sup> Imperative programming must be taught; If it is done in a later course, there is no unnecessary confusion