# Sudoku

Dave Angel 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:

<SNIP>
>>
>>
>> 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.
>>
<SNIP>
>
> 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
recursion.

(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
subdirectory.

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

--
DaveA

```