Logic of SML recursive functions

Question

Hi I'm trying to learn SML. I'm having trouble understanding the some of the recursive functions I'm coming across , for example

 fun Square (x:int, y:int)=
if y=0 
then 1 
else x * Square(x,y-1);

I understand that in the else bracket the x is being multiplied by the value of the Square function taking x and y-1 as arguments and this process will continue until y hits 0 . I'm just not clear in each step of the recursion what is x being multiplied by? Furthermore once y hits 0 why doesn't the function return 1? Thank you

molbdnilo molbdnilo · Accepted Answer · 2021-05-04T13:01:04

The function does return 1 when y = 0, but this value is returned to the caller - Square(x,1) - which returns a value to its caller, Square(x,2), and so on.
(The big secret of recursive function is that they work exactly like non-recursive functions.)

I think one of the best ways towards understanding is to use the substitution method.

Look at Square (3,2). Replacing x and y in the function definition with their values gives

if 2 = 0 then 1 else 3 * Square (3, 2-1)

2 is clearly not 0, so we need to figure out what Square (3, 1) is before we can continue with the multiplication.
Repeat the same process:

if 1 = 0 then 1 else 3 * Square (3, 1-1)

The condition is still false, so continue with Square (3,0).

if 0 = 0 then 1 else 3 * Square (3, 0-1)

Now the condition is true, so we know that Square (3,0) is 1.
Move back one level and substitute:

if 1 = 0 then 1 else 3 * 1

So, Square (3,1) is 3. Substitute again:

if 2 = 0 then 1 else 3 * 3

which makes 9, which is what you would expect.

You could also consider this (endless) sequence of non-recursive functions:

...
fun Square_3 (x, y) = if y = 0 then 1 else x * Square_2 (x, y-1)
fun Square_2 (x, y) = if y = 0 then 1 else x * Square_1 (x, y-1)
fun Square_1 (x, y) = if y = 0 then 1 else x * Square_0 (x, y-1)
fun Square_0 (x, y) = if y = 0 then 1 else x * Square_minus1(x, y-1)
fun Square_minus1 (x, y) = ...

and then think about how Square_2(3, 2) works. Square(3,2) works in exactly the same way.

(By the way, your function has a pretty odd name. You might want to rename it.)

Logic of SML recursive functions

1 Answers