Resources for Learning Recursion

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

Can’t recommend this book enough!

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.

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 .

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.

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

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

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

• Learn You Some Erlang - Recursion
• Learn You A Haskell - Recursion
• Clojure for the Brave and True - Living with Immutable Data Structures

I hope that helps!

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