[Tutor] recursive function example

[ugajin at talktalk.net]

Yes, it does :)

The indents get messed up in my mail programme, but/and 
issue running first example, it returns 1:

 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)) 

But the following worked:
    if n == 1:
        return 1
    else:
        return sum_up_to_rec1(n-1) + n
print(sum_up_to_rec1(9)) 

Interesting debug output comparing rec1 and rec2
There is I think a typo in line:
print("start of func ; n : %d" % n, end=" | ") 
I changed this to:
print("start of func ; n : %d" % n, "end= | ")


Cab now see the 'hidden' object sub_res, and the hidden sum operation, thanks! 
I am guessing, it is possible to save each sub_res object as it is generated as a variable perhaps, or grouped together as a list?

 Self-similar (fractal) recursion, sounds complex, I am guessing this is like linear recursion but simultaneously in more than one dimension?
Curious business really. Wonders, if I may be a closet programmer, or something,

Your explanation has helped, thanks. I shall look again at how the sub_res outcomes are printed :)

-A


 

-----Original Message-----
From: spir <denis.spir at gmail.com>
To: tutor at python.org
Sent: Wed, 11 Dec 2013 13:15
Subject: Re: [Tutor] recursive function example


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 
_______________________________________________ 
Tutor maillist  -  Tutor at python.org 
To unsubscribe or change subscription options: 
https://mail.python.org/mailman/listinfo/tutor 

 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/tutor/attachments/20131211/a8eb88c9/attachment.html>