[Tutor] recursive function example

[spir]

On 12/10/2013 03:48 PM, ugajin at talktalk.net wrote:
> [...]

Recursivity is hard to get really, meaning intuitively with your guts so-to-say. 
Maybe using another example may help. Lets us say you want a function that sums 
numbers from 1 up to n, the only input variable. (The result should thus be 
n(n+1)/2.)

def sum_up_to (n):
     # 'res' for result because 'sum' is a Python builtin symbol
     res = 0
     for i in range(1, n+1):
         res += i
     return res
print(sum_up_to(9))

Now, how to make this recursive? There are multiple ways, all based on:
     # intuitive def:
     sum_up_to(n) = 1 + 2 + ... + n
     # recurrence def:
     sum_up_to(n) = sum_up_to(n-1) + n
     sum_up_to(1) =  1
We want to just reproduce this second def stupidly in code:

def sum_up_to_rec1 (n):
     if n == 1:
         return 1
     else:
         return n + sum_up_to_rec1(n-1)
print(sum_up_to_rec1(9))

This does not help much and understand the recursion procedure yet, si let use 
add some debug output rightly placed:

def sum_up_to_rec1 (n):
     print("start of func ; n : %d" % n, end=" | ")
     if n == 1:
         return 1
     else:
         sub_res = sum_up_to_rec1(n-1)
         print("n : %d ; sub_res : %d" % (n, sub_res))
         return n + sub_res
print(sum_up_to_rec1(9))

Run it.

The surprising point, maybe, is that all "start of func..." outputs get written 
in a row with all "sub_res..." outputs coming on lines one under the other. This 
is the core of the recurrent logic: starting from 9, we call the func for 8; 
nothing is yet computed, no result (thus nothing to print as sub_res). From 8, 
we call the func for 7; nothing is yet computed, still. Etc... until 1, our stop 
value, which finally returns a result. This result for 1 permits the call for 2 
to (write the sub_res for 1 *at the end of the big row* and) complete, which 
permits the call for 3 to (write the sub_res for 2 and) complete... etc until 9. 
The call for 9 is out initial run, when it returns with its product, this is the 
final result.

Thus, the logic is such: the execution cascade falls here top-down; but the
computation cascade inverts gravity and climbs down-up.

Does this help?

Now, why do we execute top-down? After all, the definition by recurrence allows 
us very well to start from 1 and go up to n, it would work as well, so why not? 
The reason is that we would need to keep n aside, since in this case it becomes 
our stop value; but we still need some index, here going up from 1 to n. Thus, 
we need another parameter to the recurrent func, say like in the easy func 
above. And in fact we need yet a third parameter, namely the partial result: how 
else would the next call know the partial result? This gives something like:

def sum_up_to_rec2 (n, i=1, sub_res=0):
     # 'res' for result because 'sum' is a Python builtin symbol
     print("start of func ; i : %d ; sub_res : %d" % (i, sub_res), end=" | ")
     if i == n:
         return i + sub_res
     else:
         sub_res += i
         print("sub_call ; sub_res : %d" % sub_res)
         return sum_up_to_rec2(n, i+1, sub_res)
print(sum_up_to_rec2(9))

Needless to say, this is more complicated (but strangely far easier to 
understand for me). Another solution is to _define_ a new function, recursive, 
inside the outer one which thus keeps a simple interface (no 'i' or 'sub_res'). 
This is very often needed in recursion in functional programming, because we 
need to pass partial data anyway (state of partial execution). In fact, your 
case and mine are not typical.

Thus, if we must define a new function anyway, we have the choice of running 
upwards or downwards; downwards is the normal case for a weird reason, namely 
that the typical data structure there is a linked list, to which one can only 
(efficiently) put new items at start; thus, if we run forwards, the results are 
backwards.

Advice: use recursion whenever it corresponds to the application; meaning the 
idea you are expressing itself is recursive. This is the case in problems which 
decompose into sub-problems *of the same form*. Otherwise, avoid forcing 
recursion whenever it drives to a distortion of ideas.

There are situations where, like in our 2 cases, a simple conception is a linear 
recursion (recursion just mean repetition, literally re-running), while an 
alternative view is of self-similar recursion, like fractals (what we call 
recursion in programming, see self-similarity in wikimedia). I used to program 
both views to get used to recursive thinking.

Denis