Reproducing Nest-function with recursive nesting does not work

Question

In general, when I am learning a new programming language, it helps me to understand how builtin functions works. I am trying to reproduce the builtin Nest[f,exp,n] without any fancy Mathmatica functions.

This is what I want:

nesting[f_,k_] := Nest[f,#,k]&
=> nesting[f,3][Pi] = f[f[f[Pi]]]

I thought about implementing a recursive function:

nesting[f_,k_] := nesting[f,k-1]
nesting[f,1] := f[#]&

But unfortunately, this does not work. Trying to evaluate the function at some point does add this function evaluation to the outermost, not the innermost function.

=> nesting[f,3][Pi] = f[f[f[#1]&]]][Pi]

It seems that the ampersand (&) from the definition of a pure function has to be outside the whole nested function. That means I want to have following structure:

nesting[f,3] = f[f[f[#1]]]&

For that I tried changing my function definition to

nesting[f_,k_] := nesting[f,k-1]&
nesting[f_,1] := f[#]

This yiedls a (atleast for me) unexpected and definitely unwanted behaviour:

nesting[f,3] = nesting[f,3-1]&
nesting[f,3][Pi] = nesting[f,2-1]&

Why does the second parameter (k) change depending on if I evaluate the function or just want to get the pure function from $3-1$ to $2-1$? And how can I fix my function in general?

Answer 1

Here's a few examples to play with:

Clear@nest;
nest[f_, 1] := f;
nest[f_, k_] := f @* nest[f, k - 1];

First thing to note is that f and f[#]& are basically the same here. "f" is represents the function named "f". "f[#]&" represents "the function that you get if you apply f to some argument". Those are basically the same.

Here's a more confusing solution, which I think follows a bit more directly from what you're trying to do:

Clear@nest;
nest[f_, 1] := f[#]&;
nest[f_, k_] := f[nest[f, k - 1][#]] &;

It's weird and gross. I'd find this very confusing. Maybe the best way to write this is to include all the arguments:

Clear@nest;
nest[f_, 1][arg_] := f[arg];
nest[f_, k_][arg_] := nest[f, k - 1][f[arg]];

Answer 2

@Searke Thank you for your quick answer! I am answering here because giving complex answers in comments is horrendously unreadable when you try to include code. Additionally to that, I need more then the few characters that are allowed in comments.

Unfortunately, it does not really solve my problem completely.

Let us begin with your first solution

Clear@nest;
nest[f_, 1] := f;
nest[f_, k_] := f @* nest[f, k - 1];

That does work, but does not produce the wanted

nest[f_,3] = f[f[f[#]]]&

and also used the builtin Function "Composition".

Unfortunately, your solution

Clear@nest;
nest[f_, 1] := f[#]&;
nest[f_, k_] := f[nest[f, k - 1][#]] &;

does not really work for me. The function will not be evaluated at some recursion point.

nest[f,k] = f[nest[f, 3 - 1][#1]] &

It seems to be the same problem as I was having before. Is there a problem on my part? It seems that the function does not have a pattern that it can match to because of the double double brackets and remains unevaluated?

Your solution

Clear@nest;
nest[f_, 1][arg_] := f[arg];
nest[f_, k_][arg_] := nest[f, k - 1][f[arg]];

would work in principle but does not produce the wanted result

nest[f,3][Pi] = f[f[f[Pi]]]
nest[f,3] = nest[f,3]

Why will nest[f,3] not result in a pure function but remain unevaluated? Is there a way to archieve

To be clear:

I am trying to produce a pure function that expects one parameter, such that

nest[f,k] = f[f[f[.......f[f[f[#]]]......]]]&

that means, I want Mathmatica to return a pure function even when I am not evaluating at a certain point.

Clear@nest;
nest[f_, 1][arg_] := f[arg];
nest[f_, k_][arg_] := nest[f, k - 1][f[arg]];
nest[f_, k_] := nest[f, k][#] &

This will result in

nest[f,3] = nest[f,3][#1]&

I am feeling that we are just there, how can I force Mathematica to evaluate the last

nest[f,3][#1]

to

f[f[f[#1]]]

?

EDIT:

As an example, when using the builtin "Nest"

Clear@nest;
nest[f_, k_] := Evaluate[Nest[f, #, k]] &

I am getting

nest[f,3] = f[f[f[#1]]]&

This is the desired behaviour.

EDIT2:

Hey, I was able to solve the problem using nasty recursive pure functions:

nest[f_,k_]:=Evaluate[If[#1==1, f[#2], f[#0[#1-1, #2]]] &[k, #]]&

This leads to the expected behaviour:

nest[f,3]=f[f[f[#1]]]&