# Pr. Euler 18, recursion problem

Aidan aweraw at gmail.com
Mon Oct 6 08:13:18 CEST 2008

```process wrote:
> I am trying to solve project euler problem 18 with brute force(I will
> move on to a better solution after I have done that for problem 67).
> http://projecteuler.net/index.php?section=problems&id=18
>
> However I can't get the recursive function right.
>
> I always have to use return right? Unless I am printing? So I canät
> stack to diffferent recursive calls after each other like so:
> recur_left(t, p)
> recur_right(t,p+1)
>
>
> Some stuff I have tried:
>
> def recur(tree, pos):
>     if not tree:
>         return []
>     else:
>         return [[tree[0][pos]] + recur(tree[1:], pos)] + \
>                [[tree[0][pos]] + recur(tree[1:], pos+1)]
>
>
>>>> recur([[1],[2,3],[4,5,6]],0)
> [[1, [2, [4], [4]], [2, [5], [5]]], [1, [3, [5], [5]], [3, [6], [6]]]]
>
>
> SO it is kind of working, just not exactly like I want.
> A more easily parseable/readable result would be nice, I want to be
> able to sum() over each path preferrably.
>
> So the result should be:
> [[1,2,4],[1,2,5],[1,3,5],[1,3,6]]
>
>
>
> I know conceptually what has to be done.
> Base case: empty tree, return []
> Else: recur to the left and to the right.

This is just my opinion, but I felt the non-brute force solution to this
problem was actually simpler than trying to define a brute force
recursive solution.... I tried to implement a brute force algorithm at
first, until I had an epiphany with regard to how simple the problem
actually was.  Then I faced palmed.

```