Types of Recursion (Part 2) | Tail & Non-tail Recursion

[@babatundelawal8096]

After searching everywhere for a proper explanation to tail recursion. I found this. This is great, thank you

[@hosmjrshinh2675]

9:06 My dear friend let me tell you one thing😘

[@sayeedhasansaim8355]

Both of theme are non-tail recursion. 😊

[@josuequintero-td5gh]

Does the function stop being called when n overflows?

[@mustafaabozaina2787]

Tail recursion performance is considered better than Non-Tail recursion because tail recursion is the last line executed so there's nothing left to do before leaving the function, this helps the compiler to optimize the execution because the function's stack frame need not be saved

[@aj.arunkumar]

this should hv been included in the video.. thanks

[@zhiyizhu3040]

Thank you so much! I have been confused whole day about the concept of tail recursion, you just help me to have a good night sleep~

[@RitikSharma-pc5yj]

same happen with me today...I thought, just wasted my whole day but this video cleared my whole concept. hence my hard work pays off that I found this video....thankyou so much.

[@nihalpandey5675]

Same here

[@lakshmiprasannachilukuri8814]

I request neso academy to give answers to the home work problems in the comment section...It will be even better if u explain them...

[@hetaeramancer]

@Curtis Phoenix no one gives a damn with your instapwn and your second dummy acc...

[@laus-thecurious4120]

Absolutely right

[@kushagraacharya4629]

Your message has been successfully read and ignored ✓✓

[@tejavathusrilaxmitejavathu5224]

@@laus-thecurious4120 Good

[@sardarzain1066]

Yeah

[@bhanukumar3364]

Sir ,why I not met such Teacher during my Graduation, Thanks a lot for wonderful teaching.

[@irfansari_]

Bro I am in Graduation. and I thing I am lucky to find this teacher

[@bhaskarjyotigogoi9236]

Both are Non Tail Recursive function. In Program 2 the range of int from -2^(31) to +2^(31)-1....When n=2^31 then it exceeds the range of int and again start from -2^(31) which is less than 0..

[@nuwaver91]

Are they both Non Tail Recursive because printf is the last thing in the function?

[@nishantraj9762]

@@nuwaver91 yeah both are non tail recursive function

[@p.gaurav.n.m2417]

i am very happy that u people are helping us in almost all subjects.On behalf of all , my very big thanks to Neso Academy.......

[@adnansarkar9219]

both program 1 & 2 are non-tail recursion functions, But program 2 has no step to go base so it will be infinite.

[@aydinfurkancan]

@@s.oktaydonmez649 adamsın knk iyi akıl ettin

[@sardarzain1066]

Give signed value brother eg -10

[@ergenbalik]

@@s.oktaydonmez649 helal

[@sruthimajhi5610]

It has a base cond.

[@jsmphompho8052]

@@s.oktaydonmez649 thank you, I also forgot about this fact

[@shradhajadhav5609]

It's really helpful video, I always confused about recursion function but now everything is cleared about recursion

[@RAHULYADAV-zr5fq]

Hii

[@omchoudhary4931]

Seriously you are doing a great job for all of us . ✌️✌️ Thank you so much 💓💓

[@sri7169]

you guys doing a great job helping people WHO LOOKING out for knowledge # EDUCATION IS NOT A BUISNESS

[@iuseyoutubealot]

100% it shouldn't be

[@indhujag5920]

Both are non-tail recursion. I executed Program 2 in Visual Studio Code. I took n=3.I got output and it prints from 3,6,12 upto byte limit and again return that from byte limit to 3. Program 2 is not infinte loop. It executes upto the byte limit of the computer and last line is also executed after return.

[@randomguy8577]

Thanks 😊

[@twiz8859]

But in second program indeed value got true and finally if got executed but there is a printf before recursive procedure and after if being executed, there is, that printf statement left to be executed and second thing we didn't put rescursive procedure in else construct which mean still recursive procedure got executed anyway and in program 1 when value got zero recursive again isn't in else construct it still executed value 0;

[@meenalsolanki9286]

Your videos really helped me out to understand many things on recursive exactly to the point.

[@a_k1817]

Till now i can say that your LEGENDRY TEACHER

[@AdityaSingh-ii4km]

❤

[@SRI-PRIYAN]

Most of the people think that the 2nd program is wrong and does not converge into the base case but it actually converges... It ia because int overflow even when the output is 1(the smallest positive number) the recursion can run only upto 32 times because an int is 4 bytes which is 32 bits... At n=1 the first bit is set and when n=2 second bit is set and so on... When it reaches the 32nd bit n is no longer a positive number and the program returns.

[@kevint3522]

Great comment! I'm glad I scrolled down and found it. Thank you!

[@SandhyaSingh-ms6br]

Part 1 and part 2 both are great examples of non-tail recursion, in fact, 2nd code is very useful if you want to revise the concept of range of "int" along with studying type of recursion, ..... In the same code(2nd homework code) if we change any one of the two printf statements and print 2*n instead of n, then we'll notice that as the size of n doubles each time during recursive calling then as it reaches 1073741824, the recursive function that will be called by fun2(1073741824) will be fun2(-2147483648) [since max value of int is 2147483647] and as -214.... is less than zero therefore the base condition is met and thereafter the second printf statement will start getting executed and the functions will simultaneously pop out from the stack. The output obtained in this case (where we are printing 2*n instead of n clearly shows this)

[@shreyapatel1400]

Well explained thnk you dear

[@godfather5777]

This comment should be pinned. Thanku🙌

[@sidharthjain2129]

We will get a palindrome r8? In program 2

[@prodiptamondal1758]

thanks

[@abdousaadi2715]

cool explanation i thought the program would last forever thank you

[@Post-random_post]

Amazing lectures i never see this type of explaination aswome

[@rking2788]

Your voice is impressive and the way u teach is amazing

[@SejalSakhare-y3u]

Ans=> PR-1: non-tail recursion function output : 0 (zero) PR-2:non-tail recursion function it is infinite loop.

[@aakashverma8602]

both are non-tail recursive function as recursion calll is not the last thing done by funcion

[@addagallanaresh4044]

print f is also be a functon

[@adarshverma013]

No only 1st is non-tail because in 2nd function will never return and last printf will never get evaluated so here only function call is the last thing done so tail recursive. No Sorry last printf will be evaluated as integer overflow will occur and n

[@omaranas2965]

@@adarshverma013 why last print will never evaluated?

[@damnnations9308]

@@omaranas2965 because it is an infinite loop

[@omaranas2965]

@@damnnations9308 aha ty bro

[@muhammadalidildar]

@0:50, fun function has type void and yet it is returning some value at line 6 of the code.

[@omkargulave5774]

It is returning void function so it is absolutely fine. And other easy way to understand is fun(n) returning to fun(n-1). And if function is void it doesn't mean that function doesn't return anything it returns void.

[@ravikumarsunkhesvarapu9122]

Thank you so very much for your wonderful lectures, Sir!!

[@Trippykiyay]

This is the best explanation of recursion that I’ve ever seen.

[@devkinandansharma7558]

sir I can see your hard work in your videos

[@QQ-gn7tc]

This channel shoud be given an award from @KZbin.

[@rudranshnemade6299]

Yes both the 2 programs are non tail recursive because the recursive call is not the last thing done by function and in both the process we need the previous function record.

[@sahryun]

if thats the case there exist no tail recursion at all, tail recursion should be removed from textbooks

[@DandelionHope]

A very big thanks to you sir for clearing my doubts on recursion

[@robertsedgewick1266]

Brilliant explanation, stack frames were very well illustrated!

[@kennymccormic7578]

Sir, thinks so much for that! I've finally got it!

[@ninoherrera3944]

Well explained great job Neso Academy!

[@RishiSingh-dj9ou]

Such a great teacher @jaspreet sir

[@tanviranjum6463]

Both of them are non - talil recursive function.🙂🙏

[@viveknirmal4811]

PROGRAM 1 = NON TAIL RECURSIVE PROGRAM 2 = TAIL RECURSIVE AS LAST PRINTFF WILL NOT GET EVALAUTE BUT IT LEADS TO STACK OVERFLOW

[@tokomnyori6730]

The printf does evaluate. I've tested both programs and found out that both are non-tail recursive. I entered an input of 8, after hitting 1073741824 it went down to -2147483648 and triggered the base case. After the integer overflow, it prints the result in reverse. Please explain if I'm wrong.

[@selvamsaravanan1095]

@@tokomnyori6730 u r ri8

[@tokomnyori6730]

@@selvamsaravanan1095 Thanks 😊

[@darshitgajjar5199]

Exactly true

[@thebeatifulnature3142]

Vivek nirma you are right 1.non tail and 2. Tail because printf is not evolut it may be leads to stack over flow so printf function not be evoluted so it is an tail recursive and in program 1. Fun2(0) arises and then printf should be evoluted so it is non tail

[@Chillvibe77]

Your style of explaination is excellent ♥️

[@Marianojoey]

Thanks to your Recursion videos not only did I understand this issue, but also learnt something. So thanks. :D

[@Aabara_ka_dabara]

please also make one vide on void functins and return 0 ,return 1 diffrence

[@kousalyakommula1322]

sir your channel is a boon for us

[@BeastGaming-hq6yu]

1 2 non tail 1) value can be zero 2) value can not be zero as well 1) n=4 then 4/2=2 2%2=0 done. 2) n=1 then pt=1 , 2*1= 2 , pt=2 goes on... value wont be zero any value after zero can never be greater then zero.

[@Hgh38]

Finally got it! You are a hero!

[@ashishchawla90]

very beautiful explaination ..great work

[@niteshmodi5468]

If teacher like you would be there in college then the scenario of student's life would be different...

[@entrtnmnthub5357]

yep...i agree :")

[@dr.nicksiz8251]

Thank you all for these videos, my master. Probably you did intently but in the end , program 2 will get an stack overflow error. That doesnt satisfy the base statement.

[@kathanparekh6135]

2:28 Sir VOID return type wala function kuch return nahi karta instead use INT as return type

[@riathakur3936]

A very big THANKS...... You are really doing a very great job ..... I was really very confused about tail and non-tail both ..... Even after asking my lecturer thrice I won't be able to get it properly..... But u made me understand ...... A very big THANKS again.....

[@arasahmad9176]

Because of your legendary lectures, now I fell in love with India.

[@atharvakulkarni3007]

1st is Non Tail but 2nd there is no base condition therefore it'll be in an ∞ loop but I can guess it as Tail because there there is nothing to do after calling the function in the function

[@AbhishekKumar-kk6qs]

Your answer is absolutely correct but there is base condition given(n

[@kumarparaskaran7598]

@@AbhishekKumar-kk6qs but when 2*n will exceed the integer range based on computer, then n will become negative( let us assume if int is 2 byte then after 32766 n will become -32768) and it will return, so I guess that 2nd is also non tail recursive

[@aninditpanigrahi3334]

@@kumarparaskaran7598 this is the correct analysis !

[@azcrypto1565]

both are non-tail recursive function because 2nd function is dependent upon the value you passed, if it will be greater number then the value multiplied with 2 will doubled and so on therefor 3 or 4 values are only printed by 1st printf function and then value will be negative (you know signed int concept) so 2nd printf will execute,too. for ex you can pass n as 536870900(nearer value of max signed value/4) so you get only 3 values WHICH is printed by 1st printf and 3 values which are printed by 2nd printf(which is same but in reverse position). SO, AT THE END NOTH ARE NON-TAIL RECURSIVE FUNCTION

[@indhujag5920]

No, Program 2 is non - tail recursive. Check out output in Visual Studio code.

[@cs21deepalijaiswal84]

Thank you so much sir for these lectures.C is our building block and you r letting us learn all our concepts with so ease.Warm regards!!!

[@shivdix]

Hey depali would you got placed I m from ur clg

[@0x656e]

My dear friend you're the best 🙌❤

[@RhaenyraT2001]

why was the activation record of fun(0) not stored in the stack in example 1?? The activation record is stored when a function is called right? fun(0) was called.

[@codingawarenes]

Veryy nice explanation thank u sir

[@kera2403]

In case of tail recursion there is no need to maintain the stack because the function call is the last thing thats happening. That is why tail recursion is preferred.

[@KuldeepSingh-rm2nr]

Best channel to learn data structure....loved it😍

[@sagnikmukherjee6604]

This was a great explanation of the topic that was about to drive me crazy... Thanks and keep it up

[@ismailyakini592]

we can't use return in a void function like what did you do in the example of the tail recursion

[@otetumooluwaseun3948]

The 1st program is a non-tail recursive, but the 2nd one is a tail recursive program. That is because the recursion will enter an infinite recursion making it impossible for the printf to be executed. Therefore, the recursion remains the last thing to be called.

[@tanjibmahammad1216]

Thanks for this, Sir. It saves a bunch of time of mine.

[@zawzawwin2918]

Problem 1 is non-tail recursive and Problem 2 is infinity loop ........ I don't know please anyone know it explain me ...

[@rachitsingh8040]

yes there should be a return after printf. void func(int k){ if(k==0){ return; } func(k-1); printf("%d",k)' return; }

[@nik-ys8ki]

no u r wrong it will stop at the same value which will be passed to it

[@kushalavardhan]

It must be like this. void func(int k){ if(k==0){ return; } return func(k-1); printf("%d",k); }

[@azcrypto1565]

both are non-tail recursive function because 2nd function is dependent upon the value you passed, if it will be greater number then the value multiplied with 2 will doubled and so on therefor 3 or 4 values are only printed by 1st printf function and then value will be negative (you know signed int concept) so 2nd printf will execute,too. for ex you can pass n as 536870900(nearer value of max signed value/4) so you get only 3 values WHICH is printed by 1st printf and 3 values which are printed by 2nd printf(which is same but in reverse position). SO, AT THE END NOTH ARE NON-TAIL RECURSIVE FUNCTION

[@manvithavemulapalli2535]

really good viedio I have ever seen tq neso academy!!!

[@mr.schrodinger7]

1st is non tail recursive. 2nd is tail recursive

[@arvindersingh9863]

Program 2 : base case not correct; Will execute till the stack overflow

[@daverussell4052]

what if the n is negative value?

[@tusharmathur5360]

@@daverussell4052 for neg it will not overflow

[@bhavyaj3069]

I think for negative value it will return back to main() [or the function that called it] Because.. the if condition becomes true so it returns back to the function that called it..

[@arunkumarkurapati8093]

Both of the given questions are the examples of non-tail recursive functions. As we are performing a modulo operation in the printf statement of first program and printing the value of n in the second program.

[@abhaypratap9898]

Please suggest any book for such questions 🥺🥺🥺

[@tokomnyori6730]

I've tested both programs and found out that both are non-tail recursive. I think the second program is not infinite because integer has its limit and it overflows and becomes zero or negative value. I entered an input of 8, after hitting 1073741824 it went down to -2147483648 and triggered the base case. Please explain if I'm wrong.

[@konstantinrebrov675]

Both are non tail recursive. Why? Tail recursion is if the recursive function call is in the tail of the function, and there are no more operations like printing or multiply *. If there is nothing to be done after the next recursive function call, all the local variables calculations already happened and we don't need them anymore. In other words after executing the next recursive function call we will not need to access any data in the current stack frame anymore. If we do not need to access any data in the current recursive function call, we can just overwrite the current stack frame with the next stack frame. For both programs we are printing the int n after we are making the recursive function call, after we return. However, the value of int n is different for each recursive function call. Therefore the compiler has to store runtime stack to save us the state of the previous recursive function calls. If after we return from the recursion we will not use any local variables any more, we are telling the compiler to not save the current state of the runtime stack. So the compiler sees that the recursion is in the tail, and after that the function does not access any local variables so it can simply over write the current stack frame with the next stack frame.

[@jacquelinepang7853]

^ I believe this

[@jagdeepsingh-tv4ty]

program 2 will fallback ,it will not go into infinite loop may be the stack has limited memory

[@bhuwan9991]

program 1 is non tail recursive , but I can't say about program 2 because it will call itself again and again. since n*2 will increase the value passed to the fun2 and it will never go to the end condition i.e. n

[@dagadoom]

I guess the integer overflow explains the function getting terminated

[@indhujag5920]

No, Program 2 is non - tail recursive. Check out the output in Visual Studio code.

[@nehagull1052]

sir can you please make a video on binary recursion??

[@nik-ys8ki]

program 1 - not-tail program program 2: this program is very interesting though . if u paas a value than it will stop at that same value because when it exceeds the range of data type it has to come back.

[@lakshitavij8600]

Can u please send me solution of these homework problems

[@lakshitavij8600]

I can't solve this

[@indhujag5920]

@@lakshitavij8600 Program 2 is non - tail recursive. Check out output in Visual Studio code.

[@nickbeats9883]

This activation record thing is cool

[@charuarora6621]

Recursion is my fear point in C programming 🙌🏻 but if(!rocketscience){printf("It can be learned ");

[@abigailbusch754]

This was so incredibly helpful!!!

[@krishpatil9609]

I assumed n==5; When fun(2*5) will be called, it will start to print 5 10 20 40.......1342177280 Iteration/recursion is possible until value of n reaches 2147483647(max range for signed int) Since we are using fun(2*n) i.e. when value of n reaches 1342177280 then after 2*n will exceed the range of n i.e. fun(2684354560) , i.e. value of n will become -ve (lec 8). And as stated if(nn i.e. n=1342177280 i.e. fun(2*671088640) and fun will pop out then 671088640 then fun will popp .... ..... n=10 i.e. fun(2*5) Now fun(2*5) will popp out and control will return to main and then main will popp out.

[@krishpatil9609]

This is for 2nd program.

[@azcrypto1565]

both are non-tail recursive function because 2nd function is dependent upon the value you passed, if it will be greater number then the value multiplied with 2 will doubled and so on therefor 3 or 4 values are only printed by 1st printf function and then value will be negative (you know signed int concept) so 2nd printf will execute,too. for ex you can pass n as 536870900(nearer value of max signed value/4) so you get only 3 values WHICH is printed by 1st printf and 3 values which are printed by 2nd printf(which is same but in reverse position). SO, AT THE END NOTH ARE NON-TAIL RECURSIVE FUNCTION

[@sowbhagyalakshmi7984]

This channel ❤❤

[@AbdallahAnalyst]

i really appreciate this effort thank you very much❤❤❤❤

[@Rani_6329]

Thank you so much....very useful 👍

[@anjaneyuluperam6076]

both r non tail recursive functions

[@paurushgargtube]

Such a good explanation

[@rushikothari1261]

Program 2 will make function call until Stack overflow condition occur. Hence the Output is Stack overflow Error. And it is Tail recursion

[@nandinisunkara4070]

How is it tail? If the condition changes,It will be non-tail.

[@rushikothari1261]

@@nandinisunkara4070 Does 2nd printf Executed atleast 1 time ? Ans is No.. Therefore, programs are just like Pf() Recursive()

[@tokomnyori6730]

Not stack overflow, integer overflow. Stack overflow is different than integer overflow. Both are non-tail recursive. In the second program, integer will hit its limit and will become negative negative number and it will hit the base case. It is non-tail recursive because it will evaluate the printf statement below.

[@rushikothari1261]

@@tokomnyori6730 In which data structure Integer are stored in Computer?

[@indhujag5920]

No, Program 2 is non - tail recursive. Check out output in Visual Studio code. Func will just executes upto the Byte limit and starts returning back and last line is executed.

[@belwizdadimed3967]

The stack usage is the same. you didn't show the optimization (by compiler) gained from the fact that it's a tail recursion. Someone can argue about the need to differentiate them since we may assume that explicit/implicit return is the last instruction that triggers the stack pop().

[@konstantinrebrov675]

use gcc -O2 to enable tail recursion in C.

[@belwizdadimed3967]

Konstantin Rebrov you didn't understand my point and hrnce you're responding to a question I didn't ask

[@vaibhavshreenamdev8392]

sir in homework problem there is a function called main( ),its not mentioned so where should i start execution ?? i'm confused....

[@madugulajoshi5050]

Same doubt

[@006daredevil]

you have to assume any number and assume that fun2() function is called from main() function and passing a value to it.

[@ashu3128]

int main() { printf(''%d'',fun2(any number here)); }

[@MuhammadNaveed_51]

great job man

[@april63382]

hi, i want to ask question about the function in 08:49. I dont understand what the purpose of this function , for example, when n=4 the output:2, when n=3, the output:1. what are the meanings of the results? thank you.

[@mohit6807]

It's so silly of me to reply your comment because now you already know the answer but As 3/2=1.5 but it is an integer variable so it will ignore the values after the dicmal Hope you get it know 😜😜

[@nuwaver91]

Are they both Non Tail Recursive because printf is the last thing in the function?

[@niteshmodi5468]

Thanks for the lecture especially the tail recursion part which was very confusing for me..

[@maksberlec4832]

Both functions are non-tail. They all have printf after the function call.

[@madhusudansahu5482]

2nd is not a recursive program

[@maksberlec4832]

@@madhusudansahu5482I do not know how you came to this conclusion. The second function is recursive for sure because it call itself. The recursion is also non-tailed. The n variable become negative because it overflows at 2^31 (integer variable). After that the second printf gets executed. Finally I tested my conclusion with the program: #include #include void fun2(int n) { if (n

[@anshikayadav7857]

Can u explain the line of yours "n becomes negative bcz it overflows at 2^31." a bit more. I'm not able to grab this concept clearly.

[@d_agudo]

thank you very much for this amazing video! helped me out!!

[@saumyashrivastava30]

Good video 👍

[@rounakbiswas3590]

Sir will you not update the videos in reasoning and aptitude Playlist?? You said there will be 250 videos but alas there are only 20. Thanking you in advance.

[@saifahmedsunny]

Thankyou neso academy

[@shikshitverma1684]

Sir plesse give the answer of homework problem in the next video for satisfaction.

[@yaxinee]

Thank u that what i needed

[@chitrangreddy6479]

1 st one is non tail recursive and second one is tail recursive ...❤

[@brocklesnarufcchamp1]

How come the second one is tail recursive?

[@anshiporwal2624]

@@brocklesnarufcchamp1 perhaps there is nothing to evaluate after function calling they simply print n

[@unknownfacts8929]

Both are non-tail recursive 😊

[@DSAbyraj1729]

thank you sir .well expalained

[@engineer_b_a_b_u]

@neso Academy Here void fun(int n) is void type then you're writing return statements. Is it not an error??

[@andistheinforitbutso7513]

Awesome 👌

[@shanthiyasekar7317]

First program is non tail recursive function and the second one is infinite