CODEWITHSUNDEEP
ocamltail-recursion
Oleg
Oleg

Reputation: 1559

Tricky recursive (tail) function examples

I never liked to play with definitions , especially at interviews. As I know :

EDIT:

A tail recursive function is a function which doesn't do any more computations after its recursive call.

I think the 2nd one is not tail recursive because it doesn't make a recursive call at all , so hence not tail recursive.

But the 1st one is tail recursive even though it makes 2 recursive calls , it doesn't do anything after that , so I guess I used my definition of tail recursivness here correctly.

let rec func x =
    if x > 10 then x else func (func (x+1))  

let f a b = a + b

Upvotes: 1

Views: 165

Answers (1)

J_mie6
J_mie6

Reputation: 730

Your definition of a recursive function is that of a tail recursive function. A recursive function is simply defined as a function that calls itself at some point in its execution. The definition also allows for functions that are indirectly recursive, i.e. they call another function that calls the original function again (where this chain can be of arbitrary length).

You are right in thinking that the second of your functions is not recursive at all. However, the first function is not tail recursive.

If we move this function to Scala we get;

@tailrec
def func(x: Int): Int = 
{
    if (x > 10) x
    else func(func(x+1))
}

the @tailrec annotation tells us if something is tail recursive. However, the compiler informs us there is a recursive call not in tail position. Namely, the inner of the two calls. A tail recursive function requires that all calls to the function are in a tail position, not just that the final call is in a tail position

Upvotes: 1

Related Questions