recursion in programming

Page 1 of 1

12 Replies - 664 Views - Last Post: 05 January 2019 - 05:54 AM

#1 RyanMco

Reputation: -9
• Posts: 93
• Joined: 27-December 18

recursion in programming

Posted 01 January 2019 - 01:57 PM

Well, what's up guys?
I've read the concept of recursion in programming and totally understand it, but really I feel like something still not understand it in recursion because it's something not used on our life/lives, may anyone give me analogues of our life that visualize the concept of recursion and its process? it would be much appreciated and sorry if that question was silly but it's really benefit me to understand well the recursion whenever I have an analogues to our life.

thanks

Is This A Good Question/Topic? 0

Replies To: recursion in programming

#2 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12491
• Posts: 45,626
• Joined: 27-December 08

Re: recursion in programming

Posted 01 January 2019 - 01:58 PM

See here.

#3 modi123_1

• Suitor #2

Reputation: 14687
• Posts: 58,690
• Joined: 12-June 08

Re: recursion in programming

Posted 01 January 2019 - 02:54 PM

There is also this site.
https://www.cs.usfca...Algorithms.html

#4 Skydiver

• Code herder

Reputation: 6664
• Posts: 22,744
• Joined: 05-May 12

Re: recursion in programming

Posted 01 January 2019 - 04:17 PM

+1 to Modi for linking to my Alma mater.

#5 RyanMco

Reputation: -9
• Posts: 93
• Joined: 27-December 18

Re: recursion in programming

Posted 01 January 2019 - 04:27 PM

Thanks guys, another question which I dont want to open a thread for !

if I have a recursive call which takes complexity time O(log n) this means at every iteration I have different n, but how it's actually O(logn) if I have different n? am I adding all O(logn) at every n?
for example:
```sort(A,p)
int i=0;
sort(A,p-1) // this assuming takes time complexity T(n/2)
sort(A,p+1) // this assuming takes time complexity T(n/2)
sort_merg(A,p-1,p+1) // this assuming takes time complexity O(n)

```

my question again, is it actually would take O(n) for every n in recursive call, right? meaning for calculating total time complexity of my algorithm I must add in totall for every n, its own time complexity which is O(n) in other words I must add o(1)+o(2)+o(3)+o(4)+o(5)+......+(n) , am I right?!

#6 modi123_1

• Suitor #2

Reputation: 14687
• Posts: 58,690
• Joined: 12-June 08

Re: recursion in programming

Posted 01 January 2019 - 04:33 PM

What? Typically you just take the worst case and that's it.

#7 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12491
• Posts: 45,626
• Joined: 27-December 08

Re: recursion in programming

Posted 01 January 2019 - 04:46 PM

You are not correct. It sounds like you are attempting to describe Mergesort, albeit incorrectly. Mergesort partitions the array in to two equal parts, each of size n/2. You clearly are not doing this in your pseudo-code.

Assuming Megresort partitions the array in to equal halves for recursive calls, we have that each call takes time T(n/2). There are two calls, which yields 2T(n/2). Merging takes time O(n). So the runtime of Mergesort is T(n) = 2T(n/2) + O(n).

Now the recursive calls reach the base case after log2(n) calls. So the "recursion tree" has height log2(n). At each level in the recursion tree, we are taking O(n) steps (where n is the "original" n). So the runtime is Theta(n log(n)).

Quote

o(1)+o(2)+o(3)+o(4)+o(5)

Little-o and Big-O are different. Note that o(1) = o(5) (and similarly, O(1) = O(5)). We say that f(n) = o(g(n)) if f(n)/g(n) -> 0 as n -> infinity.

#8 RyanMco

Reputation: -9
• Posts: 93
• Joined: 27-December 18

Re: recursion in programming

Posted 01 January 2019 - 11:51 PM

macosxnerd101, on 01 January 2019 - 04:46 PM, said:

At each level in the recursion tree, we are taking O(n) steps (where n is the "original" n). So the runtime is Theta(n log(n)).

my problem is here, "we are taking o(n) steps (where n is the "original" n) ... what do you mean by that? isn't n is different from node to node? for example at original root , the number of nodes is n, but if I go to the left subtree so there "n" is different from original n, so we take the original n or taking the different n of the node that on rooted at?!
for example if I have tree with height 3 , there would be 2^3 elements, so first it would be O(8) and afterwards I got to the subtree(left/right) which the height would be 3-1=2 so there would be 2^2 elements at height 2 ...etc, at the end we sum O(n) like this : (at first level o(n) which n is 8)o(8) + (at second level o(n) which n is 4))o(4) +(at third level which n is 3)o(3) because at every node "n" is different and accordingly to what he being called in the called function.

to sum up, doesn't O(n) mean the time complexity at every level is O(n) which n at every level is different so we are doing like this : O(n) at the "n" level, and o(n-1) at level "n-1"....at level 1 we do o(1) so at the end, the total work we do: O(n) + O(n-1) +.........+O(1) .

This post has been edited by RyanMco: 02 January 2019 - 12:04 AM

#9 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12491
• Posts: 45,626
• Joined: 27-December 08

Re: recursion in programming

Posted 02 January 2019 - 12:18 AM

Quote

my problem is here, "we are taking o(n) steps (where n is the "original" n) ... what do you mean by that? isn't n is different from node to node?

Note that Big-O is different from little-o. I used Big-O O(n), not little-o o(n). If you're going to discuss runtime complexities of algorithms, you absolutely need to understand Big-O, little-o, and Big-Theta. These are standard in any algorithms textbook like CLRS, Kleinberg, etc. Please make the effort to read up on them.

Quote

my problem is here, "we are taking o(n) steps (where n is the "original" n)

I am taking care to note that n refers to the size of the original input array, and not the sizes of smaller instances from the recursive calls.

Quote

for example at original root , the number of nodes is n

No... did you even read my tutorial on recursion?

Quote

so first it would be O(8)

Again, you are using Big-O notation incorrectly.

The type of algorithm analysis you are attempting is comparable with a senior-level theory course. Your questions indicate you are taking (or have not taken) freshmen level intro to programming and data structures courses. It is important to master the basics before biting off bigger concepts. For now, I would advise that you work on implementing and designing basic recursive algorithms rather than analyze the complexity of recursive algorithms like mergesort.

#10 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 12491
• Posts: 45,626
• Joined: 27-December 08

Re: recursion in programming

Posted 02 January 2019 - 12:33 AM

Also, this was cross-posted three weeks ago, with some good answers.

#11 RyanMco

Reputation: -9
• Posts: 93
• Joined: 27-December 18

Re: recursion in programming

Posted 02 January 2019 - 12:55 AM

macosxnerd101, on 02 January 2019 - 12:33 AM, said:

Also, this was cross-posted three weeks ago, with some good answers.

but I didn't understand well their example that's why ! and nothing else sir .. it's really pointless to post again if I understand the problem/question

#12 RyanMco

Reputation: -9
• Posts: 93
• Joined: 27-December 18

Re: recursion in programming

Posted 05 January 2019 - 02:25 AM

modi123_1, on 01 January 2019 - 02:54 PM, said:

thanks ! but what's the good approach for solving in recursion way to code? I mean what I understand we implicitly assuming that something is right and from there we up with problem(for example quicksort(array from 1 to 5 elements) assuming the elements are already sorted)

ty.

#13 Skydiver

• Code herder

Reputation: 6664
• Posts: 22,744
• Joined: 05-May 12

Re: recursion in programming

Posted 05 January 2019 - 05:54 AM

The approach is to analyze each level of recursion, and then multiply over each of the levels of recursion. There is no magic bullet.

Page 1 of 1

 .related ul { list-style-type: circle; font-size: 12px; font-weight: bold; } .related li { margin-bottom: 5px; background-position: left 7px !important; margin-left: -35px; } .related h2 { font-size: 18px; font-weight: bold; } .related a { color: blue; }