Klíčová slova
Moduly
Knihovní funkce

## Flattening lists of lists

Recusion is commonly used to process structures that contain other similar structures in itself.
In this case a sum of numbers contained in a complex structure built from lists is computed.
Zdroj: (recursion2-1.py)
```  1   l = [[1,2,3],
2        [4,5,6],
3        [7,8,9,[10,11,12],13],
4        [,,],
5        [1,3,5,,[],[5,6]]]
6
7
8   def deep_sum( xs):
9       s = 0
10       for x in xs:
11           if type( x) == type( []):
12               s += deep_sum( x)  # the recursion continues for lists
13           else:
14               s += x             # but stops for simple values
15       return s
16
17   print deep_sum( l)```
stdout:
```124
```
Doba běhu: 13.9 ms
The same function run on a simpler data structure demonstrates the order in which steps are evaluated. We could call such an algorithm depth-first, because it completely evaluates one item before going to try another.
Zdroj: (recursion2-2.py)
```  1   l = [[1,2,3],
2        [4,5,6],
3        [,,],
4        [[],[5,6]]]
5
6
7   def deep_sum( xs):
8       s = 0
9       for x in xs:
10           print x
11           if type( x) == type( []):
12               s += deep_sum( x)  # the recursion continues for lists
13           else:
14               s += x             # but stops for simple values
15       return s
16
17   deep_sum( l)```
stdout:
```[1, 2, 3]
1
2
3
[4, 5, 6]
4
5
6
[, , ]

1

2

3
[[], [5, 6]]
[]
[5, 6]
5
6
```
Doba běhu: 14.2 ms
A small adjustment of the algorithm can be used to convert the complex list structure to a flat list.
Zdroj: (recursion2-3.py)
```  1   l = [[1,2,3],
2        [4,5,6],
3        [7,8,9,[10,11,12],13],
4        [,,],
5        [1,3,5,,[],[5,6]]]
6
7
8   def flatten( xs):
9       s = []
10       for x in xs:
11           if type( x) == type( []):
12               s += flatten( x)  # + is used for list concatenation, we could also use s.extend( flatten( x))
13           else:
14               s += [x]          # we could also use s.append( x)
15       return s
16
17   print flatten( l)
18   print sum( flatten( l))  # the sum should be the same as for the first example```
stdout:
```[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 1, 2, 3, 1, 3, 5, 7, 5, 6]
124
```
Doba běhu: 13.9 ms