I played around with domi27's idea and came up with this. I made a nested array as my tree, ['link']['sublinks'] is null or another array of more of the same.
Templates
The sub-template file to recurse with:
<!--includes/menu-links.html-->
{% for link in links %}
<li>
<a href="\{\{ link.href }}">\{\{ link.name }}</a>
{% if link.sublinks %}
<ul>
{% include "includes/menu-links.html" with {'links': link.sublinks} %}
</ul>
{% endif %}
</li>
{% endfor %}
Then in the main template, call this (kind of redundant 'with' stuff there):
<ul class="main-menu">
{% include "includes/menu-links.html" with {'links':links} only %}
</ul>
Macros
A similar effect can be achieved with macros:
<!--macros/menu-macros.html-->
{% macro menu_links(links) %}
{% for link in links %}
<li>
<a href="\{\{ link.href }}">\{\{ link.name }}</a>
{% if link.sublinks %}
<ul>
\{\{ _self.menu_links(link.sublinks) }}
</ul>
{% endif %}
</li>
{% endfor %}
{% endmacro %}
If you want to use a macro in the same template, you should use something like this to stay compatible with Twig 2.x:
{% macro menu_links(links) %}
{% import _self as macros %}
{% for link in links %}
<li>
<a href="\{\{ link.href }}">\{\{ link.name }}</a>
{% if link.sublinks %}
<ul>
\{\{ macros.menu_links(link.sublinks) }}
</ul>
{% endif %}
</li>
{% endfor %}
{% endmacro %}
{% import _self as macros %}
<ul class="main-menu">
\{\{ macros.menu_links(links) }}
</ul>
This extends random-coder's answer and incorporates dr.scre's hint to the Twig documentation about macros to now use _self, but import locally.
Twig >= 2.11
As of Twig 2.11, you can omit the {% import _self as macros %}, as inlined macros are imported automatically under the _self namespace (see Twig announcement: Automatic macro import):
{# {% import _self as macros %} - Can be removed #}
<ul class="main-menu">
\{\{ _self.menu_links(links) }} {# Use _self for inlined macros #}
</ul>
If you're running PHP 5.4 or higher, there is a wonderful new solution (as of May 2016) to this problem by Alain Tiemblo: https://github.com/ninsuo/jordan-tree.
It's a "tree" tag that serves this exact purpose. Markup would look like this:
{% tree link in links %}
{% if treeloop.first %}<ul>{% endif %}
<li>
<a href="\{\{ link.href }}">\{\{ link.name }}</a>
{% subtree link.sublinks %}
</li>
{% if treeloop.last %}</ul>{% endif %}
{% endtree %}