Python-Ref > Recursion > Simple recursion explained
 
 

<-^^->
Klíčová slova
Moduly
Knihovní funkce

Simple recursion explained

Some programming languages (Lisp, Haskell etc.) use recursion as the only means of iteration over sequences.
The following example shows a simple recursive implementation of the sum function similar to what one would write in Haskell.
Expand/Shrink
Zdroj: (recursion3.1.py)
  1   def sum2( xs):
  2       if len( xs) == 0:
  3           return 0
  4       else:
  5           return xs[0] + sum2( xs[1:])
  6   
  7   
  8   print sum2( range( 10))
stdout:
45
Doba běhu: 14.5 ms
The following, slightly modified example shows the progress of the recursive function.
Expand/Shrink
Zdroj: (recursion3.2.py)
  1   def sum2( xs):
  2       print "called with", xs
  3       if len( xs) == 0:
  4           return 0
  5       else:
  6           s2 = sum2( xs[1:])
  7           print xs[0], "+ sum2(", xs[1:], ") =", s2
  8           return xs[0] + s2
  9   
 10   
 11   print sum2( range( 10))
stdout:
called with [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
called with [1, 2, 3, 4, 5, 6, 7, 8, 9]
called with [2, 3, 4, 5, 6, 7, 8, 9]
called with [3, 4, 5, 6, 7, 8, 9]
called with [4, 5, 6, 7, 8, 9]
called with [5, 6, 7, 8, 9]
called with [6, 7, 8, 9]
called with [7, 8, 9]
called with [8, 9]
called with [9]
called with []
9 + sum2( [] ) = 0
8 + sum2( [9] ) = 9
7 + sum2( [8, 9] ) = 17
6 + sum2( [7, 8, 9] ) = 24
5 + sum2( [6, 7, 8, 9] ) = 30
4 + sum2( [5, 6, 7, 8, 9] ) = 35
3 + sum2( [4, 5, 6, 7, 8, 9] ) = 39
2 + sum2( [3, 4, 5, 6, 7, 8, 9] ) = 42
1 + sum2( [2, 3, 4, 5, 6, 7, 8, 9] ) = 44
0 + sum2( [1, 2, 3, 4, 5, 6, 7, 8, 9] ) = 45
45
Doba běhu: 13.7 ms