CODEWITHSUNDEEP
scalarecursionfunctional-programmingsmlml
blue-sky
blue-sky

Reputation: 53816

Cannot understand 'functions as arguments' recursion

I'm taking a functional programming languages course and I'm having difficulty understanding recursion within the context of 'functions as arguments'

fun n_times(f , n , x) = 
    if n=0
    then x
    else f (n_times(f , n - 1 , x))

fun double x = x+x;

val x1 = n_times(double , 4 , 7);

the value of x1 = 112

This doubles 'x' 'n' times so 7 doubled 4 times = 112

I can understand simpler recursion patterns such as adding numbers in a list, or 'power of' functions but I fail to understand how this function 'n_times' evaluates by calling itself ? Can provide an explanation of how this function works ?

I've tagged with scala as I'm taking this course to improve my understanding of scala (along with functional programming) and I think this is a common pattern so may be able to provide advice ?

Upvotes: 2

Views: 287

Answers (4)

Keyel
Keyel

Reputation: 144

It is the same recursion thinking what you know already, just mixed with another concept: higher order functions.

n_times gets a function (f) as a parameter, so n_times is a higher order function, which in turn is capable to apply this f function in his body. In effect that is his job, apply f n times to x.

So how you apply f n times to x? Well, if you applied n-1 times

n_times(f , n - 1 , x)

, then you apply once more. 

f (n_times(f , n - 1 , x))

You have to stop the recursion, as usual, that is the n=0 case with x.

Upvotes: 0

Rex Kerr
Rex Kerr

Reputation: 167891

Just expand by hand. I'm going to call n_times nx to save space.

The core operation is

nx(f, n, x) -> f( nx(f, n-1, x))

terminating with

nx(f, 0, x) -> x

So, of course,

nx(f, 1, x) -> f( nx(f, 0, x) ) -> f( x )
nx(f, 2, x) -> f( nx(f, 1, x) ) -> f( f( x ) )
...
nx(f, n, x) -> f( nx(f,n-1,x) ) -> f( f( ... f( x ) ... ) )

Upvotes: 4

pad
pad

Reputation: 41290

Function n_times has a base case when n = 0 and an inductive case otherwise. You recurse on the inductive case until terminating on the base case.

Here is an illustrative trace:

   n_times(double, 4, 7)
~> double (n_times(double, 3, 7)) (* n = 4 > 0, inductive case *)
~> double (double (n_times(double, 2, 7))) (* n = 3 > 0, inductive case *)
~> double (double (double (n_times(double, 1, 7)))) (* n = 2 > 0, inductive case *)
~> double (double (double (double (n_times(double, 0, 7))))) (* n = 1 > 0, inductive case *)
~> double (double (double (double 7))) (* n = 0, base case *)
~> double (double (double 14)) 
~> double (double 28)
~> double 56
~> 112

Upvotes: 3

Erma K. Pizarro
Erma K. Pizarro

Reputation: 61

If n is 0, x is returned.

Otherwise, f (n_times(f , n - 1 , x)) is returned.

What does n_times do? It takes the result of calling f with x, n times, or equivalently: calls f with the result of n_times(f, n - 1, x) (calling f n-1 times on x).

Note by calling f i mean for example:

calling f 3 times: f(f(f(x)))

calling f 2 times: f(f(x))

Upvotes: 6

Related Questions