Recursion - What would be the complement of it?

[waive15]

Hi there,

Recursion - What would be the complement of it?

1. Recursion sounds a little bit scary to me. Wouldn't it be nicer Embedding instead?

2. Russian doll matryoshka /matr-    -    mother/

3. Coming To America..."Where's the Spoon"...Eddie Murphy as Saul the Jewish Guy

[Strange]

45 minutes ago, waive15 said:

Recursion sounds a little bit scary to me. Wouldn't it be nicer Embedding instead?

Not sure why it would be scary. After all, recursion is just repeated embedding.

In computing, recursion is, in principle, unlimited. But you eventually run out of resources (typically, memory).

And in language, recursion is limited by our brains. I can't remember the figure, but it seems that people are limited to a depth of about 3 or 4-ish(?)

49 minutes ago, waive15 said:

Coming To America..."Where's the Spoon"...Eddie Murphy as Saul the Jewish Guy

What??

[studiot]

I don't know what you want to discuss recursion in relation to  ??

 

When I was young there was a brand of coffee essence that came in a bottle.
The picture on the label showed a waiter holding a tray.

On the tray was a bottle of the coffee... with a picture of a waiter holding a tray with bottle of coffe on it............

 

 

I used to wonder about how many waiters there were.

 

34 minutes ago, Strange said:

In computing, recursion is, in principle, unlimited

Sometimes it can come to a conclusion. There is a whole mathematical theory of 'recursion formulae'.
This used to be a way of solving equations and obtaining tabulated data in the days before modern computers.

[waive15]

Hi Strange, hi studiot,

Thanks for reply.

Recursion is scary for me because:

1. You study it in school, even not in math classes but rather when they teach you some program LANGUAGE. The idea is new to the students and that makes it scary;

/LANGUAGES were scary/

2. Although solutions achieved  are elegant they almost always seem odd;

3. Prior to the 8-th/9-th grade I didn't feel, perceive it. You see - SOMETHING IMPORTANT exists and you DON'T know about it/don't see it. It is very scary that you(I) are not aware of something important.

 

*  *  *

Studiot asked "... in relation to what". Thank you, that was dead center. That was the question.

 

People noticed/discovered/ Recursion and Named it but ITS MORE OBVIOUS COMPLEMENTARY maybe they didn't bother to Name or Named it with different Names(in different ways)./Where's the Spoon???/

 

I will rephrase: Recursion WORKS, but  WHAT WORKS when we don't use Recursion(what do we call that).

 

 

Thanks again and have a nice day.

 

 

 

 

 

Edited December 6, 2019 by waive15

[Sensei]

22 hours ago, waive15 said:

1. Recursion sounds a little bit scary to me.

Yes, it is scary.. It might end up with crash of application, see example code:

void foo() {
  foo();
}

Programmers tend to avoid recursion.

Edited December 6, 2019 by Sensei

[Strange]

1 hour ago, waive15 said:

I will rephrase: Recursion WORKS, but  WHAT WORKS when we don't use Recursion(what do we call that).

The alternative to recursion is iteration. Recursion can always(?) be replaced with a loop. It is just that sometimes it is more natural to think of the problem in terms of recursion. For example, there is a sorting algorithm where you split the list of numbers in two and sort each half; but to sort each half, you split them in two and sort those halves. But then to sort those, you split them in two and sort those. You do this until you just have two numbers to sort. Then you combine each (sorted) sub-list. 

2 minutes ago, Sensei said:

Programmers tend to avoid recursion.

Not in my experience. Have you ever written a parser?

[waive15]

Thank you guys,

Let me see if I understood you right:

/on the example of  studiot . Pictures are the same/

1. If we have Picture in Picture - it is a Recursion;

2 If we have Picture next to/after Picture -  it is a Iteration.

/                        number 1/ number2/ number 3 ...                                   /

So these two ideas ARE the only Two and if it is not the One then it is the Other(they are complement to each other) And we use no other ideas in General(even outside math and computer science). If it is that simple(just two ideas, I should study the Recursion.

 

Thanks

 

Edited December 6, 2019 by waive15

[studiot]

47 minutes ago, Sensei said:

Yes, it is scary.. It might end up with crash of application, see example code:

void foo() {
  foo();
}

Programmers tend to avoid recursion.

 

45 minutes ago, Strange said:

Not in my experience. Have you ever written a parser?

 

14 minutes ago, waive15 said:

Let me see if I understood you right:

 You are all correct.

See here

Quote

Difference Between Recursion and Iteration. Recursion and iteration both repeatedly executes the set of instructions. Recursion is when a statement in a function calls itself repeatedly. The iteration is when a loop repeatedly executes until the controlling condition becomes false.

 

https://techdifferences.com/difference-between-recursion-and-iteration-2.html

The Maths I was referring to earlier is called recurrence relations

Quote

We have seen that it is often easier to find recursive definitions than closed formulas. Lucky for us, there are a few techniques for converting recursive definitions to closed formulas. Doing so is called solving a recurrence relation. Recall that the recurrence relation is a recursive definition without the initial conditions.

http://discrete.openmathbooks.org/dmoi2/sec_recurrence.html

 

Edited December 6, 2019 by studiot

[waive15]

Thank you studiot,

I am rolling up my sleeves.

[Sensei]

22 hours ago, Strange said:

In computing, recursion is, in principle, unlimited. But you eventually run out of resources (typically, memory).

Recursion might end up with overflow of CPU stack, if it is not properly coded (starting from depth limit, dynamically checking available left stack space etc.).

Reminding you, default Windows OS thread has 1 MB CPU stack size. It is easy to cause overflow. The more arguments passed on stack to function, the more local variables, the quicker it will happen.

Recursion is typically replaced by software stack to not have to call the same function in the loop.

1 hour ago, Strange said:

Not in my experience. Have you ever written a parser?

At the moment, I am making my own PDF parser. Whether parsing requires recursion strongly depends on what kind of data are being parsed. e.g. mathematical equation can use nested parenthesis, so recursion might be used to handle them.

Ray-tracing is better example of algorithm that relies on recursion. I even know some 3D applications which were crashing due to overflow of stack when too many reflective and/or refractive objects have been put in the scene and fired rays back and forth between surfaces. Therefor need for option "Ray Recursion Limit" in such engines.

25 minutes ago, waive15 said:

I am rolling up my sleeves.

Start from Wikipedia article about recursion:

https://en.wikipedia.org/wiki/Recursion_(computer_science)

 

Edited December 6, 2019 by Sensei

[waive15]

Thank you Sensei,

 

Have a nice day!

[Strange]

Worth noting that although you can always replace recursion with a loop, it is not always straightforward. However, in the case of "tail recursion" (where the last thing the function does is call itself) then this can be trivially converted to a loop. Compilers will sometimes do this automatically (to save on stack space, as Sensei says).

3 hours ago, waive15 said:

Recursion is scary for me because:

1. You study it in school, even not in math classes but rather when they teach you some program LANGUAGE. The idea is new to the students and that makes it scary;

The idea shouldn't be new. When I was little, there was a joke story that we would tell:

Quote

Some pirates were stranded on island. It was a dark and stormy night so the captain said to the mate "Tell us a story mate", and this is the story he told: Some pirates were stranded on island. It was a dark and stormy night so the captain said to the mate, "Tell us a story mate", and this is the story he told: Some pirates were stranded on island ...

 

[Eise]

[waive15]

Hi Strange,

I probably might have heard something, I don't recall, but even now when I read this never ending story I feel bored, I lose concentration and  do not connect it with Recursion - definition of which I already know. It needs mental capacity. But i like Escher's drawings and paintings of Rene Magritte.

Just now i noticed that you are  from Italy. After i learned to read I read: The Adventures of the Little Onion; Gelsomino in the Country of Liars and Fairy Tales Over the Phone.

Now I see picture which Eise has posted. I get hypnotized not thinking at all of recursion. If you have seen Poirot series with David Suchet, there was ABC murders. One of the main characters was very suggestible. I am more like that type of person - suggestible. When i see film i practically don't think much. Example is The Big Lebowski. I instantly liked it and didn't know why.

Then came Internet/Youtube and I searched for opinions and meaning of the film. My favorite explanation is: Why 'The Big Lebowski' Is Secretly 'Alice In Wonderland' /in Youtube/.

Again i digressed from the theme.

 

Thanks for the reply

2 minutes ago, waive15 said:

Hi Strange,

I probably might have heard something, I don't recall, but even now when I read this never ending story I feel bored, I lose concentration and  do not connect it with Recursion - definition of which I already know. It needs mental capacity. But i like Escher's drawings and paintings of Rene Magritte.

Just now i noticed that you are  from Italy. After i learned to read I read: The Adventures of the Little Onion; Gelsomino in the Country of Liars and Fairy Tales Over the Phone.

Now I see picture which Eise has posted. I get hypnotized not thinking at all of recursion. If you have seen Poirot series with David Suchet, there was ABC murders. One of the main characters was very suggestible. I am more like that type of person - suggestible. When i see film i practically don't think much. Example is The Big Lebowski. I instantly liked it and didn't know why.

Then came Internet/Youtube and I searched for opinions and meaning of the film. My favorite explanation is: Why 'The Big Lebowski' Is Secretly 'Alice In Wonderland' /in Youtube/.

Again i digressed from the theme.

 

Thanks for the reply

 

4 hours ago, Strange said:

Worth noting that although you can always replace recursion with a loop, it is not always straightforward. However, in the case of "tail recursion" (where the last thing the function does is call itself) then this can be trivially converted to a loop. Compilers will sometimes do this automatically (to save on stack space, as Sensei says).

The idea shouldn't be new. When I was little, there was a joke story that we would tell:

 

 

[Clear Kets]

I remember an introduction I had to the SML programming language. SML does not even provide a loop construct in the basic out-of-the-box syntax.

The classic recursion disaster, even given a termination condition, is computing the nth number in the Fibonacci sequence. There are 2ⁿ recursive calls. I forget whether tail recursion helps with this challenge.

I thought I had down the MathML/LaTeX that worked for me in my first post, but the math-fu isn't there today, not even for a simple exponent 2 to the n.

Edited December 8, 2019 by Clear Kets

[Strange]

21 minutes ago, Clear Kets said:

I thought I had down the MathML/LaTeX that worked for me in my first post, but the math-fu isn't there today, not even for a simple exponent 2 to the n.

There is a slight bug in the Forum software: the LaTeX is not properly rendered until you refresh the page.

I discovered ML when I was at college and wrote a simulator for a processor using it. For "fun".

[waive15]

Hi guys,

This awful Recursion again. We have established that Recursion and Iteration are complementary.

Recursion: Pic(1) has Pic(2) has Pic(3)      -    Pic(1) before Pic(2) before Pic(3)   :  Iteration

But

Recursion:                         Pic(1) has Pic(2) has Pic(3)      Top--->Down Direction

Down--->Top Direction  Pic(3) is Pic(2) is Pic(1)              : Definition

Can we say that Recursion and Definition are complementary in some other way?

 

Thanks and have a nice time.

[Strange]

53 minutes ago, waive15 said:

Recursion: Pic(1) has Pic(2) has Pic(3)      -    Pic(1) before Pic(2) before Pic(3)   :  Iteration

But

Recursion:                         Pic(1) has Pic(2) has Pic(3)      Top--->Down Direction

Down--->Top Direction  Pic(3) is Pic(2) is Pic(1)              : Definition

These directions seem arbitrary: it depends how you visualise/draw these. There is no inherent direction to either.

54 minutes ago, waive15 said:

Can we say that Recursion and Definition are complementary in some other way?

Maybe, if you define what you mean by "complementary".

[waive15]

Hi Strange,

Thank you for you reply. That was just an idea: in Iteration you "have two directions right - left", commands go one after the other and probably have a number in that sequence.

I suspected(speculatively) that that could be said about Recursion also: go down/dive in/submerge (the one direction) and go up/ emerge (the other direction). And the direction UP we probably may call it Definition because (i am speculating) I don't know what is the definition of the Definition. So it was a shot in the dark. Pure guess work.

So if:

Pic(1) has Pic(2) has Pic(3) ...                   and

... Pic(3) is Pic(2) is Pic (1)

we have is/has as "complementary" to each other(in some way) and this looks simple and beautiful. But is it right?!   If Recursion is so important then

Recursion        -         Iteration    (complementary in some way)

Recursion        -        Definition    (complementary in some other way) 

/Just kidding, as Alf would say/

 

Strange, it is very kind of you that you reply, I don't want to waste your or anybody's time. I will never become a programmer.  All about computers - programming, managing operating  systems, networking  is so demanding for me.

The joke:

Leonard talks with Sheldon about Penny. And he say that in general there is a chance between them something to happen. His argument is that He is a male and She is a female. And

Sheldon responds : "But from different species, Leonard, from different species."

 

You guys and I are from different species.

 

Thanks and have a nice day.

 

13 hours ago, Strange said:

These directions seem arbitrary: it depends how you visualise/draw these. There is no inherent direction to either.

Maybe, if you define what you mean by "complementary".

/pressed quote just for the notification/

[waive15]

Hi there,

I will go strait to the business. Let's say Recursion and Embedding are synonymous. You probably think that I don't go to the pages(links you send me). I go and I read. Again about Embedding - it is visual to me and I prefer This name before Recursion( no associations with it in my head).

Two types of Embedding as  I recall:

f calls f

f calls g call f

I love to watch movies(who doesn't)

Movies go:

1. Event after Event( it is okay, it is a standard story) or

2. Let's take Heist with Gene Hackman and Danny DeVito the two Masterminds. Here goes Embedding f calls g calls f ... The mightier goes deeper and wins!

This also we see between two Opposing secret agencies, the 1st tap the 2nd and the 2nd pretends  that  it doesn't know, crossing - double crossing and so on...

Jackie Brown, but there there are 3 parties f, g, h.

Sleuth(1972) with Michael Cain - what is the Embedding it is hard to me to decide.

There probably other possibilities.

 

Am I close?

 

Thanks

[Sensei]

18 hours ago, waive15 said:

f calls f

f calls g call f

These two are both examples of computer recursions..

18 hours ago, waive15 said:

There probably other possibilities.

"Sky is the limit".. therefor programmer might not realize his or her code is actually doing internally recursion (which suddenly will lead to overflow of stack and failure at the end, after too many repetitions)...

 

[waive15]

Thank you Sensei for you reply. I am leaving the forum to study more seriously and not bother you with my silly questions. You guys were great. Thank you again.

Edited December 15, 2019 by waive15

[Sensei]

2 hours ago, waive15 said:

Thank you Sensei for you reply. I am leaving the forum to study more seriously and not bother you with my silly questions. You guys were great. Thank you again.

Hardcore version of recursion: programmer (aka "God") is making simulation of the Universe, then in that simulation of the Universe there are appearing simulated intelligent entities (aka "Gods") who are making their own simulated Universes, in which there are appearing simulated ^ 2 intelligent entities (aka "Gods") are making simulation of the Universe.. ... and so on, so on...

In the limitless Universe, where energy is freely made ("infinite"), it could go forever, and ever..

If you are able to create simulated Universe, you are indistinguishable from the God.. Are you able to do so, you mortal entity, reading my words.. ?

 

Edited December 15, 2019 by Sensei

[waive15]

Thank you Sensei, goodbye.