Recursion in Python and Scala

Question

Why does this Scala recursion

def foo(id:Int): Int = { 
    if (id == 0) { return id } else { foo(id - 1) }
}
foo(2)

returns 0, while this Python recursion returns None?

def foo(id):
    if id == 0:
        return id
    else:
        foo(id - 1)
foo(2)

In which way do Python and Scala handle recursion and manage nested activation records?

Answer 1

In Scala, any block is evaluated to the value of it's last statement. For example, you can write:

val myVal = {
  val t = 1
  val r = 8
  t + r
}

Here, myVal would evaluated to 9.

Similarly, your else block evaluates to the value returned from foo(id - 1) (even though there's no explicit return keyword), and therefore the value of the entire method body would evaluate to that value as long as the else block is reached (the entire if statement would be evaluated to the result of foo(id - 1), and since that if is the last (and only) statement in the method body - that would be the method's return value).

You can drop the first return keyword as well:

def foo(id:Int): Int = { 
  if (id == 0) id else foo(id - 1)
}

In Python, that's simply not the case; Only return statements signify the method's return value. If you return nothing, None is returned.

Answer 2

You either need to add a return to the else clause:

def foo(id):
    if id == 0:
        return id

    return foo(id - 1)

or do something like:

def foo(id):
    return id if id == 0 else foo(id - 1)

Answer 3

You need return in your else clause:

def foo(id):
    if id == 0:
        return id
    return foo(id - 1)

This is with return you are basically assigning a value to the function. And two, Scala does an evaluation at the last statement while Python requires the return keyword. So if foo(0) returns 0, foo(0) will then contain the value of 0. Since nothing is returned, the function doesn't have any value, which defaults to None.

By using return, you are assigning the value of foo(id-1) to foo(id). But what is it? This is where it gets recursive since to get the value of foo(id-1), it must run the function. This happens over and over until you get 0. In other words with return:

foo(n) = foo(n-1) = foo((n-1)-1) = foo(n-2) = ... = foo(n-n) = foo(0) = 0

You can watch the steady decrease of id/n here.