Resources for Learning Recursion

On @AstonJ’s suggestion, I decided to start a thread on recursion. It’s one of my biggest mental hurdles to get over while learning FP. (My OOP brain just wants to iterate through everything.)

I’ve scoured the Internet for good resources on recursion, but I’ve come up empty. So far, I’ve seen suggestions of reading through The Little Schemer to really learn how to think recursively. I’m also doing the problems in Dave Thomas’s Programming Elixir, but I’m only able to wrap my head around the simpler problems.

Do you guys have any tips on how to think recursively?

2 Likes

How far through the book are you? This might help us get an idea of which bits you have covered.

These online books on functional programming are good resources to learn FP concepts and recursion:

I hope that helps!

2 Likes

I’m currently in the middle of Chapter 10, which is the Enumerables section.

1 Like

Actually, I don’t think recursion is hard, It’s quite easy if you’re familiar with C.

Example in C:

#include <stdio.h>

void recurse ( int count ) /* Each call gets its own copy of count */
{
  printf( "%d\n", count );
  if (count <= 0) return;
    
  recurse ( count - 1 );
}

int main(int argc, char **argv)
{
  recurse (10);
  return 0;
}

This is basically the same thing in Elixir:

defmodule Recurse do
    def print_number(n) when n <= 0 do
        IO.puts n
    end

    def print_number(n) do
        IO.puts n
        print_number(n - 1)
    end
end
2 Likes

For Elixir it is a little bit harder than other languages. But the first thing you need to realise is, that recursion is just the natural way to define loops in functional languages.

Also, for datatypes which are recursively defined (like a linked list or trees) its rather natural to follow the structure of the datatype also with the way of function calls.

Lets say we have a struct with the fields :value, :left, and :right. You might see from the pattern that this is meant to be a simple binary tree, so lets call it Tree for now. The field :value can hold arbitrary values and the other two fields do hold another Tree or nil.

So if we want to check if a certain value is in that tree, it is the easiest to just define it like the following:

def find(%Tree{value: v}, v), do: true
def find(%Tree{left: l, right: r}, v), do: find(l, v) || find(r, v)
def find(nil, _), do: false

Also you should never ever handle anything in the multi-headed function what is not expected from your definition of your datatype. I have to say, that this last paragraph is my personal opinion, but does line up well with what you get from the typing of other languages as well with “let it crash”-philosophy from Erlang and Elixir.

A much bigger problem, I have to admit, often it is, to rewrite a not tail recursive function into a tail recursive one, by splitting it into a public API-function and a private “worker” or “do” function which does carry one or more accumulating arguments around. This of course feels like some kind of dark magic when you try it for the first time, but as you go along, try hard and learn it will get easier and easier everytime you do it. Also your ability to recognise non-tail-recursive functions on the first glance will increase.

@bthach: The problem is, that in many imperativ languages, there is still this dogma around, that recursion is a bad thing per se and blows the stack. This was true until early 1990s, but since then more and more compilers got some optimisation technics called “tail call optimisation” which does rephrase tail-recursive-calls into some looping mechanism on the targeted (virtual) machine. So in imperative languages there are the same two kinds of recursion as we have in functional: “bad” and “good” recursion, but since functional languages relied on recursion from the very beginning, they’ve used it as provided. In the imperative languages, they do have “good” and “bad” as well, but they learned that recursion were always bad. And younger devs, comming straight from university who do know it better can’t win a fight against all that old seasoned devs in industry.

Maybe the situation is a little bit better in industries that use more modern technology than C or C++, but the above paragraph shows, what I have experienced in person and what I’ve heard by co-students in similar situations.

5 Likes

When writing recursive functions, first I try to think about stop condition, i.e. when I need to stop execution and return the result.

Also I try to think of all different states function’s argument might have, and which of them are relevant for my solution.
For each of these states I write another function head.

This is of course very basic and simple approach, although it might be enough for start:) Once you get used to recursion you will miss it in classic imperative languages :smiley:.

5 Likes

I do not miss it in imperative languages. I use it. Ok I do not have nice multihead functions, but I use similar recursion patterns as in functional languages. Most of the time the functions are easier to read than their counterparts with classic loops.

2 Likes

Can’t recommend this book enough!

2 Likes


Lec 6 | MIT 6.00SC Introduction to Computer Science and Programming, Spring 2011
MIT OpenCourseWare

1 Like