Recursion

[Bengt Richter]

On Mon, 29 Sep 2003 06:06:37 GMT, Dennis Lee Bieber <wlfraed at ix.netcom.com> wrote:

>Jakle fed this fish to the penguins on Sunday 28 September 2003 08:28 
>pm:
>
>> 
>> That's great. You guys have no idea how much that helped. And I love
>> that debugging tip. For some reason I thought that the 2 statements
>> after the recursion call, "result = n * recurse" and "return result"
>> weren't executed till n == 0. If you can't tell, I'm new to this. But
>
>        They aren't executed until the "first" return from factorial() -- 
>which only happens when n /is/ 0... At that point, the recursive calls 
>start returning and executing the statements under the factorial() call.
>
>        To reduce indentation, I'll use just 3!
>
>Factorial(3)
> n has value 3
> n is NOT 0 so
> res= Factorial(n-1)
>                Factorial(2)
>                 n has value 2
>                 n is not 0 so
>                 res= Factorial(n-1)
>                                Factorial(1)
>                                 n has value 1
>                                 n is not 0 so
>                                 res= Factorial(n-1)
>                                                Factorial(0)
>                                                 n has value 0
>                                                 n IS 0 so
>                                                 return 1
>                                 res is now 1
>                                 return n * res (1 * 1)
>                 res is now 1
>                 return n * res (2 * 1)
> res is now 2
> return n * res (3 * 2)
>
>Factorial(3) returns value 6
>
>
>        Each time Factorial makes a recursive call to itself (I know, that is 
>redundant phrasing) it creates a new "block" of local variables, the 
>variables in the previous block can not be seen. When a return 
>statement is encountered, the block of locals is deleted, leaving the 
>return value visible to the calling block.      
>
>
You didn't type that out by hand, did you? ;-)

====< showfact.py >=======================================
def showfact(n, indent=0):
    sind = len(' res= Factorial(')*' '*indent
    print '%sFactorial(%s)'%(sind, n)
    print '%s n has value %s' %(sind, n)
    print '%s n %s 0 so'%(sind, ('is not', 'IS')[n==0])
    if n==0:
        print '%s return 1' %sind
        return 1
    print '%s res= Factorial(n-1)'% sind
    res = showfact(n-1, indent+1)
    print '%s res is now %s' %(sind, res)
    print '%s return n * res (%s * %s)' % (sind, n, res)
    return n * res

def test(n):
    print '\nFactorial(%s) returns value %s' % (n, showfact(n))

if __name__ == '__main__':
    import sys
    try: test(int(sys.argv[1]))
    except: print 'Usage: showfact.py <integer arg>'
==========================================================

[ 8:16] C:\pywk\clp>showfact.py
Usage: showfact.py <integer arg>

[ 8:16] C:\pywk\clp>showfact.py 2
Factorial(2)
 n has value 2
 n is not 0 so
 res= Factorial(n-1)
                Factorial(1)
                 n has value 1
                 n is not 0 so
                 res= Factorial(n-1)
                                Factorial(0)
                                 n has value 0
                                 n IS 0 so
                                 return 1
                 res is now 1
                 return n * res (1 * 1)
 res is now 1
 return n * res (2 * 1)

Factorial(2) returns value 2


Regards,
Bengt Richter