How to golf with recursion

Recursion, though not the fastest option, is very often the shortest. Generally, recursion is shortest if the solution can simplified to the solution to a smaller part of the challenge, especially if the input is a number or a string. For instance, if f("abcd") can be calculated from "a" and f("bcd"), it's usually best to use recursion.

Take, for instance, factorial:

n=>[...Array(n).keys()].reduce((x,y)=>x*++y,1)
n=>[...Array(n)].reduce((x,_,i)=>x*++i,1)
n=>[...Array(n)].reduce(x=>x*n--,1)
n=>{for(t=1;n;)t*=n--;return t}
n=>eval("for(t=1;n;)t*=n--")
f=n=>n?n*f(n-1):1

In this example, recursion is obviously way shorter than any other option.

How about sum of charcodes:

s=>[...s].map(x=>t+=x.charCodeAt(),t=0)|t
s=>[...s].reduce((t,x)=>t+x.charCodeAt())
s=>[for(x of(t=0,s))t+=x.charCodeAt()]|t  // Firefox 30+ only
f=s=>s?s.charCodeAt()+f(s.slice(1)):0

This one is trickier, but we can see that when implemented correctly, recursion saves 4 bytes over .map.

Now let's look at the different types of recursion:

Pre-recursion

This is usually the shortest type of recursion. The input is split into two parts a and b, and the function calculates something with a and f(b). Going back to our factorial example:

f=n=>n?n*f(n-1):1

In this case, a is n, b is n-1, and the value returned is a*f(b).

Important note: All recursive functions must have a way to stop recursing when the input is small enough. In the factorial function, this is controlled with the n? :1, i.e. if the input is 0, return 1 without calling f again.

Post-recursion

Post-recursion is similar to pre-recursion, but slightly different. The input is split into two parts a and b, and the function calculates something with a, then calls f(b,a). The second argument usually has a default value (i.e. f(a,b=1)).

Pre-recursion is good when you need to do something special with the final result. For example, if you want the factorial of a number plus 1:

f=(n,p=1)=>n?f(n-1,n*p):p+1

Even then, however, post- is not always shorter than using pre-recursion within another function:

n=>(f=n=>n?n*f(n-1):1)(n)+1

So when is it shorter? You may notice that post-recursion in this example requires parentheses around the function arguments, while pre-recursion did not. Generally, if both solutions need parentheses around the arguments, post-recursion is around 2 bytes shorter:

n=>!(g=([x,...a])=>a[0]?x-a.pop()+g(a):0)(n)
f=([x,...a],n=0)=>a[0]?f(a,x-a.pop()+n):!n

(programs here taken from this answer)

How to find the shortest solution

Usually the only way to find the shortest method is to try all of them. This includes:

• Loops
• .map (for strings, either [...s].map or s.replace; for numbers, you can create a range)
• Array comprehensions
• Pre-recursion (sometimes within another of these options)
• Post-recursion

And these are just the most common solutions; the best solution might be a combination of these, or even something entirely different. The best way to find the shortest solution is to try everything.