Dave Angel davea at
Fri Mar 29 00:28:27 CET 2013

On 03/28/2013 06:11 PM, Eric Parry wrote:
> On Thursday, March 28, 2013 3:06:02 PM UTC+10:30, Dave Angel wrote:

>> Are you familiar with recursion?  Notice the last line in the function
>> r() calls the function r() inside a for loop.
>> So when r() returns, you're back inside the next level up of the
>> function, and doing a "backtrack."
>> When the function succeeds, it will be many levels of recursion deep.
>> For example, if the original pattern had 30 nonzero items in it, or 51
>> zeroes, you'll be 51 levels of recursion when you discover a solution.
>> If you don't already understand recursion at all, then say so, and one
>> or more of us will try to explain it in more depth.
> Thank you for that explanation.
> No, I do not understand recursion. It is missing from my Python manual. I would be pleased to receive further explanation from anyone.
> Eric.

Recursion is not limited to Python.  It's a general programming term, 
and indeed applies in other situations as well.  Suppose you wanted to 
explain what the -r switch meant in the cp command.  "r" stands for 

(example is from Linux.  But if you're more familiar with Windows, it's 
the /s switch in the DIR command.)

The cp command copies all the matching files in one directory to another 
one.  If the -r switch is specified, it then does the same thing to each 

Notice we did NOT have to specify sub-subdirectories, since they're 
recursively implied by the first description.

Closer to the current problem, suppose you defined factorial in the 
following way:  factorial(0) is 1, by definition.  And for all n>0, 
factorial(n) is n*factorial(n-1).

So to directly translate this definition to code, you write a function 
factorial() which takes an integer and returns an integer.  If the 
parameter is zero, return one.  If the parameter is bigger than zero, 
then the function calls itself with a smaller integer, building up the 
answer as needed  (untested).

def  factorial(n):
     if n==0:
         return 1
     val = n *factorial(n-1)
     return val


More information about the Python-list mailing list