CODEWITHSUNDEEP
pythonpython-3.xrecursion
J.Doe
J.Doe

Reputation: 474

Why do my recusion functions even work? Syntax confusing

I have written two recursive functions, which work almost identically. I was trying to get the recursion right and then I accidentally stumbled upon the answer, but the syntax confuses me:

def fac(N):

    """
    Factorial of N.
    """
    ################# This makes no goddamn sense to me #################
    if N == 1:
        return N
    ####### because N == 1, yet 'return N' is the correct result ########
    elif N == 0:
        return 1

    return N*fac(N-1)

How can N == 1 be true as the exit condition but also store the result of fac(N)? Same thing with a function prod(), which is the analog to sum().

def prod(List):

    """
    Product of all numbers in a list.
    """

    if len(List) == 1:
        return List[-1]

    return List[-1]*prod(List[:-1])

I don't get how the end result is stored in List[-1]. Does the python interpreter understand return arg*func(arg) in a special way?

Upvotes: 1

Views: 54

Answers (2)

Florian Bernard
Florian Bernard

Reputation: 2569

Nothing special, but in case like this, use print and explore.

def fac(N): 
""" Factorial of N. """  
    if N == 1: 
        return N
    elif N == 0: 
        return 1 
     return N*fac(N-1)

Let see how it's work for fac(3)

# fac(3)
# fac(3) => 3 * fac(3-1)
# fac(3) => 3 * fac(3-1) => 2 * fac(2-1)
# fac(3) => 3 * fac(3-1) => 2 * fac(2-1) => return 1
# fac(3) => 3 * fac(3-1)  <= 2 * 1
# fac(3) <=  3 * 2 * 1
# 6

Upvotes: 1

seymourgoestohollywood
seymourgoestohollywood

Reputation: 1167

Consider the loops required to calculate fac(4):

1: fac(4) -> 4 * fac(3)  # It then has to calculate fac(3)
2: fac(3) -> 3 * fac(2)  # It then has to calculate fac(2)
3: fac(2) -> 2 * fac(1)  # It then has to calculate fac(1)

4: fac(1) -> 1  # Finally we've returned a value - now back up through the loops

3: fac(2) -> 2 * fac(1) == 2 * 1 == 2
2: fac(3) -> 3 * fac(2) == 3 * 2 == 6
1: fac(4) -> 4 * fac(3) == 4 * 6 == 24

The second part is effectively the same thing - recurse down until you get a value, then keep plugging that in all the way back up to your original request.

Upvotes: 1

Related Questions