lolllll

so you're telling me there are people who can solve psets with only main lecture?

When he described recursion as sexy I almost spat out my breakfast LOOOL.

sexayyy 😅

Parabéns amigo

Parabéns amigo

shoutout my boy Bryan one time

Encontrei um brasileiro🇧🇷

underrated

Literally

I paused the video and tried to do by myself, but I don't get the final example.

Doug did :D

@@kattodoggo3868 doug was born in harvard

Jan Negrey why don't u complete then?

@@jayant9151 that's what I asked myself recursively

@@KillTheAlarm69 what's your base condition?

Thanks! This helped a lot!

I did something like this too but because i was initializing the counter variable at the top it was always returning same value 😂 then i tried declaring it as static

That return+1 is confusing the hell out of me, when I wrote my version of this function I used a global variable “steps” as a counter that I would ++ increment right before the return statement if the number is even or odd. I didn’t dare mess with the return value. Wish he spent a little time explaining exactly how that return works.

@@ares106 yeah how is this working without a step counter? I also do not understand even after debugging and watching it go step by step, where is it storing the value?

@@robm7887 I used a step counter too, but i imagine that when he return 1 + the fuction itself, that + 1 is waiting to be returned to the Main function calling it, but since the recursive function is calling itself, the +1 keeps waiting... Eventually we enter in the conditional of even or odd again and we return +1 again with the recursive function, so now that +1 that was waiting transforms into a +2, so on and so on, until n == 1, wich returns 0 (+2 + 0 for example). Thats when the function is called to MAIN and return the actual amount of steps without a step counter variable... or thats my understanding of it at least haha.

@@ares106 When I initially wrote the program, I also used a global variable, but with Doug's explanation, I modified it to this: I used a variable inside main to invoke the collatz function: int steps = collatz(n); The return value gets stored in the variable "steps" and gets a sum with each recursion or something.

@@ares106 Same here. Luckily, I or we have access now to great mentor ChatGPT!!. Learning nowadays is much easier. ChatGPT: I see the confusion. In the context of a recursive function, the return 1 statement doesn't mean the end of the entire program or code; instead, it means the end of the current invocation of the function. When a function is called recursively, each invocation of the function has its own set of local variables and executes its own set of statements. The return statement is used to return a value to the caller of that specific invocation. In the Collatz sequence example: return 1 + collatz(n * 3 + 1); This line means that the current step in the Collatz sequence is being counted (represented by 1 +) before making the recursive call to collatz with the updated value. The result of this expression is then returned to the previous invocation in the recursion stack, and the steps are accumulated as each recursive call completes. So, in a recursive function, return 1 is a way to contribute a value to the final result while also continuing the recursive process. It doesn't end the entire program or code; it's

The end goal is to return the number of steps needed to get to 1. Saying return 1 + collatz is incrementing 1 for every time the function is called.

@@davidgodovich597 Watch the video on call stacks: kzfaq.info/get/bejne/l6mAntaryrG2kWg.html

@@davidgodovich597 This is so helpful. Thank you!

@@exnihilonihilfit6316 This was a perfect connector. Thank you!

Because if n == 1, it doesn't count a step. But if it's higher than 1, it should count a step for each recursion. In my code, I simply incremented steps++, then called the recursion, and it worked. However, I had to declare int steps in the main function and pass it along with the user input.

why did you set int sum = 0?

You can also use this #include #include int factorial(int number); int main (void) { int number = get_int("Enter a number: "); printf("Factorial of your number is: %i ", factorial(number)); } int factorial(int number) { if (number == 1) return 1; else return number * factorial(number - 1); }

+1

It's a counter. Try it with debug50 with +1 and without. And you'll clearly see it step by step.

so at the end gives you the the total steps required to reach 1

I also don't understand why he adds 1 to the function return value -- how are steps counted in this way? I used a counter in order to count steps.

(Copy-pasting my comment below) I got it! After completing the Collatz's algorithm, the collatz function in the base case will eventually return 0, so we can use its return value as a counter at this point. After that, the next function refers to the function that returned 0 and adds 1 to it. The next function takes the value of the function that returned 1 and adds 1 to it, and so on in recursion. The number returned by the last function will be the total number of functions involved in the recursion.

thank you so much you just help me with a question

at some point you need to return something or it will be an infinite "loop". 0 means n was already 1 to begin with so that doesn't count as a step in this case.

I think for the sake of this demonstration, they were looking to make a scenario of * 3 + 1 so that it could add more steps to the process, in which you would have to figure out how many steps it would take.

@@JonnyLovato this is an equation used all the way down into high school basic algebra. its used because they think its what should be used. its worthless and tedious when there's a better/faster way

@@donovanm.8909 what do you mean? the rules are if the number is odd, multiply by 3 and then add 1. How is just adding 1 the same thing

With recursion the program basically builds up a "call stack" until it reaches a tipping point, n = 1 in this case. Then it finishes from the inside out. So it finishes the "deepest" call first and slowly works backwards until it reaches the first call. So the code will count up from 0 one by one until the original function returns its value. Try creating something simpler first, like the factorial function and print out the states or watch it with the debugger. Imagine that you build a line of dominoes, and then you push the last one.

yes but that's not really the point is it

Hi. Each time one of the recursive cases (n is even, or n is odd) is reached, a unit will be added for the total steps to reach 1 (in both (1 + n / 2) and (1 + 3 * n)). The moment that the n / 2 operations is equal to 1, the value zero will be returned, and all ones that were "collected" in each function call will be added. If you still have any questions, you can call.

@@dhomini1140 but isn't return 1 usually used to indicate an error?

@@Narjod Not um this case. The 1 os usually returned as default in the main function. In the function created in the vídeo, the 1 is returned to be added to the total number of steps

Hi. The execution ends when n == 1 in one of the function calls. Until this, the program is going to keep calling the function recursively. The total of "1" that is added represent the total of steps(or how many times the function was called). When the program reach the base case(n == 1) all the function call will be evaluated. The last call is going to return 0, and all the other calls will return 1. After the this, the first function call will return the total of steps(represented by the sum of all the "1" from each function return)

@@dhomini1140 thx bro, you help me a lot, I have been struggling to find the reason why he put +1 in the recursive case, thanks

its counting backwards. Lets say you do collatz(4). Is 4 == 1? no is 4 % 2 == 0? Yes (even) return 1 (as in one step) + collatz(4/2) Now what is collatz(4/2)? 4/2 = 2 so: is 2 == 1? no is 2 % 2 == 0? yes return 1 + collatz(2/2) now what is collatz(2/2)? 2/2 = 1 so: is 1 == 1? yes return 0 now the program will have build this stack of function calls function like this return 1 + collatz(4/2) + collatz (2/2) + 0 which is replaced by return 1 + 1 + 1 + 0 so the final result will be 3 steps.

@@iEatBass thanks homie! I couldn't get if for shit.

@@iEatBass Thank you for this explanation, I finally got it as well!

@@iEatBass Super helpful. I'm surprised this wasn't explained in more detail in this video, as these shorts are usually so good at spending a longer time breaking down concepts from the main lecture. This is the third or fourth resource to try to understand recursion that I've followed, and it's helping, but it's still super counter-intuitive and not sexy at all, yet.

@@iEatBass In your explanation, the final result should be 2 steps no? in this part "return 1 + collatz(4/2) + collatz (2/2) + 0", idk where "return 1" came from

see call stacks: kzfaq.info/get/bejne/l6mAntaryrG2kWg.html

Because if n == 1, it doesn't count a step. But if it's higher than 1, it should count a step for each recursion. In my code, I simply incremented steps++, then called the recursion, and it worked. However, I had to declare int steps in the main function and pass it along with the user input.

Because if the value becomes 1, it returns 0, which will be added to the 1 of the previous recursive call. Thus making itself count for each of the recursive calls.

@@WicCaesar may I have your full code which you incremented the step++ instead of return 1 + ... ?

n - 1 is the last integer in a sequence (because an array starts counting from element [0], and so n - 2 is the next to last. Fibonacci starts with 0 and 1, which is n - 2 and n - 1, respectively. 0 + 1 = 1. So the sequence is 0, 1, 1. Now n - 2 and n - 1 are both 1. 1 + 1 = 2, so the sequence is now 0, 1, 1, 2, n -2 == 1, n - 1 == 2. 2 + 1 = 3; 0, 1, 1, 2, 3. What are n - 2 and n - 1 in this stage of the sequence?

Are you looking for recursion?

@@juliangallego7963 Are you looking for recursion?

@@gona3665 Are you looking for recursion?

​@@Drakonus_ Are you looking for recursion?

No because then you aren't using that return value in any way and always getting 1

I suppose you have to prompt the user for a number greater than 1.

Hi. In the fact() function, if the n is equal 0 the program is not going to enter the while loop (because n > 0 is False) and will just return product at the end (product = 1).

9:37 It's stated the conjecture applies to positive integers. They just don't do any checks of the input - for brevity, I guess.

I might be wrong but it might be because you're missing a set of parenthesis? I would guess the code doesn't know if it should be ((n % 2) != 0), or (n % (2 != 0)).

If (n % 2 == 0)

@@simonricard4403 I tried without parentheses and it worked for me. Must be something else.

I don't understand the purose of adding 1. I don't see how Doug's code calculates steps.

I got it! After completing the Collatz's algorithm, the collatz function in the base case will eventually return 0, so we can use its return value as a counter at this point. After that, the next function refers to the function that returned 0 and adds 1 to it. The next function takes the value of the function that returned 1 and adds 1 to it, and so on in recursion. The number returned by the last function will be the total number of functions involved in the recursion.

Afraid I didn't make up the Collatz conjecture, I'm only the messenger...and not good enough at theoretical mathematics to tell you why it's 3n and not n! :) en.wikipedia.org/wiki/Collatz_conjecture

n+1 would be wrong. Take 1 for n and we get 2 and 2 ain't odd. If you want make it a odd number it should be 2n+1. Take any number for n and you get a odd number. Also 3n+1 is wrong, if you choose 1 for n, you will get 4. 4 is a even number. 😬

@@javaexpertsa8947 what are you talking about? If n is 1, you follow the first step, and stop...

It's the simplest way to make sure we don't end up in a loop somewhere along the way. The conjecture is: Every positive integer will get to one eventually with these simple steps. It might blow up in the process, though!

@@javaexpertsa8947 ???... Makes 0 sense

keep adding a return statement with some value at the end of each if or else ( make sure that the return is not reached in your code)

I think that happens if you lock all of your returns behind if conditions, which is why the example code just checks for even numbers and just uses an else statement instead of else if. Also the elses aren't actually necessary since the returns will skip the elses anyway.

You need to put a return value outside of an if-statement, correct me if I'm wrong.

can you post the code?

@@jaysankhe8350 sure thing, I've simplified it a little bit, but still no luck: #include #include #include int main (void) { int n = 5; int collatz (n) { if (n == 1) return 0; else if ((n %2) == 0) return 1 + collatz(n/2); else return 1 + collatz(3n + 1); } printf("number of steps: %i", collatz); }

@@cwejter Hi! If the question is still relevant, I suggest you didn't define your function. You should first include before int main (void) a line of code, which will be a declaration of the function and after the main part you should write a definition. So, implented in a programm, it will look something like: #include #include #include int collatz(int n); int main (void) { int n = get_int("Give me an integer: "); int steps = collatz(n); printf("number of steps: %i ", steps); } int collatz(int n) { { if (n == 1) return 0; else if ((n % 2) == 0) return 1 + collatz(n / 2); else return 1 + collatz(3 * n + 1); } }

@@dirtykimono4874 damn I'm dumb. Thanks :D !

if you break without return anything, program will not execute if you input 1 to it. But it better gives the value 0 back to the user, meaning of 0 step needed if we have the number 1 already. Return function basically break after it gives a value back, so its more meaningful to use return there

@@seeknndestroy420 Thank you very much!! It's helpful!