Why Tail recursion of factorial returns none?

Question

I did factorial using tail recursion, it is returning "none" - why

def fact(n, k):
    print "n = %d k = %d" % (n,k)
    if n == 1:
        print "k final = ", k
        return k

    else:
#        print n
        print k
        fact(n-1, k*(n-1) )

a =(fact(4, 4) ) 
print a

A question dealing with recursion in Python would make for a better duplicate. — chepner, Sep 23 '15 at 20:05
@chepner It's the same pattern in almost all languages. The exception is languages like Lisp, where the last expression in a function is automatically returned. So I haven't made a collection of analogous questions for each language. — Barmar, Sep 23 '15 at 20:09
@Barmar - but I have a return k in the if clause - I thought that it would return k - why not? — user5331677, Sep 23 '15 at 20:15
That returns it to the recursive caller, but that caller doesn't have a `return` statement to pass it on. — Barmar, Sep 23 '15 at 20:17
@Barmar - I thought that when if condition is met, then else won't be executed - how come putting a return in the else has an effect? — user5331677, Sep 23 '15 at 20:22
If `n` is 2, the `else` clause is executed. It then calls `fact` recursively, which returns `2`. That returns back to the first call, which then leaves the function without returning anything. — Barmar, Sep 23 '15 at 20:25
@user5331677 Each recursive call executes its own return. The last call in the chain uses the return in the `if` condition, but all the previous calls would not. — chepner, Sep 23 '15 at 20:25
@Barmar - is "first call" is same as "if" loop? - In if loop I have a return k? — user5331677, Sep 23 '15 at 20:29
There's no such thing as an `if` loop. Loops are done with `while` and `for`. — Barmar, Sep 23 '15 at 20:30
The first call is when you do `a = fact(4, 4)`. That sets `n = 4` in the function. It then goes into the `else` clause, and executes `fact(3, 4*3)`. That's the second call. The third call is `fact(2, 12*2)`. 4th call is `fact(1, 24*1)`. That last call returns `24`. It then resumes the caller, which was in the `else` clause, so it doesn't return anything. — Barmar, Sep 23 '15 at 20:32
@Barmar - I thought if it get inside the "if", then it will not get inside "else" - if it does not get inside else, then it can not execute 'fact(n-1, k*(n-1) )'? — user5331677, Sep 23 '15 at 20:50
Wow, this comment section got recursive quickly. @user5331677, your question has already been answered by chepner 10min ago: Different calls in the call stack may follow different code paths. — Lukas Graf, Sep 23 '15 at 20:54
@user5331677 You're forgetting that the function is recursive. There are `n` calls to the function -- the first `n-1` go into the `else`, the last one goes into the `if`. — Barmar, Sep 23 '15 at 21:01
@LukasGraf - it is recursive because, explanations were lacking clarity! I am still not clear. — user5331677, Sep 23 '15 at 22:08
An `if` can contain 3 parts, predicate, consequent and alternative. like this `if( predicate) consequent; else alternative;` Either the consequent or the alternative will be run and both need to `return` a value. Computing something and not use it means the line can be omitted since you never use the result. In the end of a python function is an invisible `return None`. C++ and Python are just cousins and both Algol dialects, where the `if` came from. — Sylwester, Sep 23 '15 at 23:37

score 1 · Accepted Answer · answered Sep 23 '15 at 20:04

1

You haven't returned a value in the else clause -

else:
    fact(n-1, k*(n-1) )

This should read

else:
    return fact(n-1, k*(n-1) )

answered Sep 23 '15 at 20:04

Chris Taylor

46,912
15
110
154

it gives correct answer - but I have a return k in the if clause - I thought that it would return k - why not? – user5331677 Sep 23 '15 at 20:16
@user5331677 Yes, everytime you call it with `n==1` it will work. For `2` it will recurse to `1` which returns `k` to the original caller, which discards the returned value and returns None. For 3 the original caller gets None, which it ignores but it self return None at it's end. Every tail position needs to return something in order for it to work, not just the first. – Sylwester Sep 23 '15 at 23:49
@Sylwester - thank you – user5331677 Sep 24 '15 at 06:09

Why Tail recursion of factorial returns none?

1 Answers1