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.