[Tutor] A small (but long) introduction to recursion
alan.gauld@bt.com
alan.gauld@bt.com
Thu, 26 Jul 2001 10:48:10 +0100
> I absolutely do not understand recursion.
Don't worry it really is a weird concept until you
get your head around it - then it seems obvious! :-)
> I took your example and tried to do some tracing,
> but I do not understand how the sum is stored or
> returned:
>
> def addTo(n):
> if n == 0: return 0
> return addTo(n-1) + n
>
> x = addTo(10)
addTo(10) returns addTo(9) + 10
addTo(9) returns addTo(8) + 9
addTo(8) returns addTo(7) + 8
addTo(7) returns addTo(6) + 7
addTo(6) returns addTo(5) + 6
addTo(5) returns addTo(4) + 5
addTo(4) returns addTo(3) + 4
addTo(3) returns addTo(2) + 3
addTo(2) returns addTo(1) + 2
addTo(1) returns addTo(0) + 1
addTo(0) returns 0
So now...
addTo(1) returns 0 + 1 = 1
addTo(2) returns 1 + 2 = 3
addTo(3) returns 3 + 3 = 6
addTo(4) returns 6 + 4 = 10
addTo(5) returns 10 + 5 = 15
addTo(6) returns 15 + 6 = 21
addTo(7) returns 21 + 7 = 28
addTo(8) returns 28 + 8 = 36
addTo(9) returns 36 + 9 = 45
addTo(10) returns 45 + 10 = 55
Which is the final answer.
Does that help?
Alan G