recursion

[Neil Cerutti]

On 2007-09-14, John Machin <sjmachin at lexicon.net> wrote:
> On Sep 14, 10:04 pm, Marc 'BlackJack' Rintsch <bj_... at gmx.net> wrote:
>> On Fri, 14 Sep 2007 13:40:17 +0200, Gigs_ wrote:
>> > sorry i think that i express wrong. having problem with english
>>
>> > what i mean is how python knows to add all thing at the end of recursion
>>
>> Because you have written code that tells Python to do so.  ;-)
>>
>> >  >>> def f(l):
>> >      if l == []:
>> >          return []
>> >      else:
>> >          return f(l[1:]) + l[:1]
>>
>> > f([1,2,3])
>>
>> > recursion1   f([2,3]) + [1]
>>
>> > recursion2   f([3]) + [2]  or [2, 1]?
>>
>> > recursion3   f([]) + [3] or   [3, 2, 1]
>>
>> Both alternatives in recursion 2 and 3 are wrong.  You have to
>> simply replace the function invocation by its result which
>> gives:
>>
>>     f([1, 2, 3])
>> r1  f([2, 3]) + [1]
>> r2  f([3]) + [2] + [1]
>> r3  f([]) + [3] + [2] + [1]
>> r4  [] + [3] + [2] + [1]
>>
>> And now the calls return:
>>
>> r3  [3] + [2] + [1]
>> r2  [3, 2] + [1]
>> r1  [3, 2, 1]
>>
>> > i dont get all this
>>
>> >  >>> def f(l):
>> >      if l == []:
>> >    print l
>> >          return []
>> >      else:
>> >          return f(l[1:]) + l[:1]
>>
>> >  >>> f([1,2,3])
>> > []
>> > [3, 2, 1]  # how this come here? how python save variables from each
>> > recursion?
>>
>> There is not just one `l` but one distinct `l` in each call.
>>
>
> I reckon that what the OP wants is a simple explanation of how
> function calls use a stack mechanism for arguments and local
> variables, and how this allows recursive calls, unlike the good ol'
> FORTRAN IV of blessed memory. Perhaps someone could oblige him?
>
> I'd try but it's time for my beauty sleep :-)
><yawn>
> Good night all

I may as well stick my neck out again, since I'm already
beautiful. ;)

Another way of understanding recursion is to break it up into
seperate functions, so the spectre of a function calling itself
doesn't appear.

def f(l):
  if l == []:
    return []
  else:
    return f(l[1:]) + l[:1]

The function above reverses a list of arbitrary length. To help
understand how it works, I'll write several discreet functions
that sort lists of fixed lengths.

I start with a simple case (though not the simplest case--that
only comes with experience), reversing a two-element list:

def f2(l): # reverse a two-element list
  return [l[1], l[0]]

Next build up to the next level, writing a function that can
reverse a three-element list. The key is to be as lazy as
possible. You must figure out a way of taking advantage of the
function that reverses a two-element list. The obvious solution
is to use f2 to reverse the last two elements in our list, and
append the first element in the list to that result:

def f3(l): # reverse a three-element list
  return f2(l[1:]) + l[:1]

And so on:

def f4(l):
  return f3(l[1:]) + l[:1]

def f5(l):
  return f4(l[1:]) + l[:1]

def f6(l):
  return f5(l[1:]) + l[:1]

A definite pattern had emerged, and it should be apparent now how
to combine all those functions into one:

def f_(l):
  if len(l) == 2:
    return [l[1], l[0]]
  else:
    return f_(l[1:]) + l[:1]

But the function above breaks for lists with less than two items.

>>> f_([1])
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "<stdin>", line 2, in f2
IndexError: list index out of range

We can handle that. The reverse of a zero or one-element list is
just itself.

def f_(l):
  if len(l) < 2:
    return l
  elif len(l) == 2:
    return [l[1], l[0]]
  else:
    return f_(l[1:]) + l[:1]

And we've arrived at an OK recursive function that can handle
arbitrary length lists. It's not as simple as it could be,
however. A little intuitive leap, perhaps, will allow you to note
that the case of a two-element list can actually be handled
without a special case:

def f(l):
  if len(l) < 2:
    return l
  else:
    return f(l[1:]) + l[:1]

Final note: for reasons of tradition, base cases are almost
always set up as it was in the original function, checking for a
zero-length list, and returning a new empty list, the truly
simplest base case. Another intuitive leap is possibly required
to note that a one-element list is not a special case after all:
it's a reverse of a zero-element list with that one element
appended.

def f(l):
  if len(l) == 0:
    return []
  else:
    return f(l[1:]) + l[:1]

Clear as mud?

-- 
Neil Cerutti