In SML - Why doesn't simple recursion always return 0 if first expression met?

Question

In a simple recursion with first if expression true then 0. if steps in the recursion keeps going until that first expression is true, why isn't 0 always returned?

fun stepping (n  :  int, number  :  int)  = 
     if number > n
     then 0
     else   1 + stepping (n, number + 1)

It seems like the function stepping should add one onto number until number > n and then always return 0. Instead, it returns the number of times you went through the recursion cycle until number becomes greater than n.

The above code tests good in SML and gave me what I wanted - the number of steps incrementing by 1 until input "number" is greater than the input "n". But manually walking through the recursion steps, it seems like the return should always be 0 when the incremented "number" > the input "n". What am I missing?

Answer 1

I think you're mistaking the result of the final call to stepping in the recursive chain (which will always be zero) as being the ultimate value returned by the expression, but that is not the case. It is actually part of a larger equation that makes up the overall returned value.

For example, if we look at how the expression gets built up as each recursive call is made when evaluating stepping(3, 1), you end up with...

result = stepping(3, 1)
result = 1 + stepping(3, 2)
result = 1 + 1 + stepping(3, 3)
result = 1 + 1 + 1 + stepping(3, 4)
result = 1 + 1 + 1 + 0
result = 3

Answer 2

Let's say that I'm going to give you some money this year, according to this scheme:

• you get nothing on the first of January
• on all other days, you get one dollar more than I would have given you the day before

How much would I have to pay you today, the 20th of February?
Fifty dollars or nothing at all?
If you follow the calendar backwards, you will eventually reach January 1st, where the payment is zero, so would you expect to get nothing?

To answer your immediate question: the function does always return 0 if the first condition is met – that is, if number > n.

However, if the first condition isn't met – number <= n – it does not return 0 but 1 + stepping (n, number + 1).
It works exactly like of you called a function with a different name; that function computes a value and then this function adds 1.

It's not like returning a value from inside a loop, such as (pseudocode)

while (true)
{
    if number > n
        return 0
    else 
        number = number +1
}

which is perhaps what you're thinking about.