davea at davea.name
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.
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).
val = n *factorial(n-1)
More information about the Python-list