Go, lesson 11
A recursive function is one that calls itself. That sounds circular, but it is a natural way to solve problems that contain smaller copies of themselves: a folder holds folders, a sentence can contain a sentence, and the sum of a list is the first item plus the sum of the rest.
Every recursive function needs:
The classic example is factorial, where 5! = 5 × 4 × 3 × 2 × 1:
Trace factorial(3): it needs 3 * factorial(2), which needs 2 * factorial(1), which
returns 1. The calls then finish in reverse order: 2 * 1 = 2, then .
2 exercises to try what you just read.
3 * 2 = 6Each call gets its own copy of n. Go keeps these on the call stack, a pile of
unfinished calls waiting for answers. Forget the base case, or fail to make the input smaller,
and the pile grows until the program crashes with a stack overflow. Go's stack grows quite
large, so this usually shows up as a long hang followed by a crash rather than an immediate
error.
Slicing makes "the rest" easy to express:
nums[1:] does not copy anything; it is a new view on the same storage, so this is cheap.
Some problems split into two or more smaller problems. Counting the ways to climb stairs taking 1 or 2 steps at a time is one:
This is elegant but slow for big n, because it solves the same sub-problems again and again.
The fix is memoisation: remember answers in a map and reuse them.
Anything recursive can be written with a loop, and Go has no tail-call optimisation, so a
simple countdown is better as a for loop. Recursion shines when the data is shaped like a
tree, or when the problem naturally branches: generating combinations, exploring a maze,
solving puzzles like the Tower of Hanoi. Choose whichever makes the code clearer.
A helpful habit when writing a recursive function: trust that the recursive call works for the smaller input, and only think about how to use its answer. This "leap of faith" is what makes recursion feel simple.
The digital root of a number comes from adding up its digits, then adding up the digits of
that result, and so on until a single digit remains. For 9875: 9+8+7+5 = 29, 2+9 = 11,
1+1 = 2.
Write a recursive function digitSum(n int) int that adds the digits of n (use n % 10 for
the last digit and n / 10 for the rest), and a recursive function digitalRoot(n int) int
that uses it. Read one non-negative integer and print its digital root.
Sample input:
Sample output:
Three pegs are labelled A, B and C. Peg A holds n disks, largest at the bottom. Move
all disks to peg C, one at a time, never putting a larger disk on a smaller one.
The recursive plan for moving n disks from from to to using spare: move n-1 disks
from from to spare, move disk n from from to to, then move the n-1 disks from
spare to to.
Read n (0 to 10) and print every move as disk <d>: <from> -> <to>, then a final line
moves: <total>.
Sample input:
Sample output:
func factorial(n int) int {
if n <= 1 {
return 1 // base case
}
return n * factorial(n-1) // smaller problem
}func sum(nums []int) int {
if len(nums) == 0 {
return 0
}
return nums[0] + sum(nums[1:])
}func ways(n int) int {
if n <= 1 {
return 1
}
return ways(n-1) + ways(n-2)
}var memo = map[int]int{}
func fastWays(n int) int {
if n <= 1 {
return 1
}
if v, ok := memo[n]; ok {
return v
}
memo[n] = fastWays(n-1) + fastWays(n-2)
return memo[n]
}987522disk 1: A -> B
disk 2: A -> C
disk 1: B -> C
moves: 3