https://xkcd.com/1270/

Recursion-is-its-own-reward.go

// Prints:
// 1 2 3 4 5
// reverse
// 5 4 3 2 1

package main

import (
	"fmt"
)

type ListNode struct {
	Value string
	Next  *ListNode
}

type List struct {
	Head *ListNode
	Tail *ListNode
}

func (list *List) add(val string) {
	list.addNode(&ListNode{val, nil})
}

func (list *List) addNode(node *ListNode) {
	if list.Head == nil {
		list.Head = node
		list.Tail = node
	} else {
		tail := list.Tail
		list.Tail = node
		tail.Next = node
	}
}

func (list *List) print() {
	if list.Head == nil {
		fmt.Println()
	} else {
		fmt.Printf("%s ", list.Head.Value)
		rest := &List{list.Head.Next, list.Tail}
		rest.print()
	}
}

func (list *List) reverse() {
	head := list.Head
	if head == nil || head.Next == nil {
		return
	}
	list.Head = head.Next
	list.reverse()
	head.Next = nil
	list.addNode(head)
}

func main() {
	l := List{}
	l.add("1")
	l.add("2")
	l.add("3")
	l.add("4")
	l.add("5")
	l.print()
	fmt.Println("reverse")
	l.reverse()
	l.print()

	// test empty list
	b := List{}
	b.reverse()
	b.print()
}