7:33 I pity the fool who only watches the main lecture (even though those are great) because they'll miss gems like this. And Doug's a damn good teacher.
Jesus this was high quality and explained super well with easy concepts, I went through a bunch of tutorials that used complex terms etc... looking at u hackerrank... but thanks CS50 and Doug
If anyone else was confused during the fib sequence part when he says if n == 0 return 1, elsif n == 2 return 1 Base cases should be if n == 0 return 0, elsif n == 1 return 1, else fib(n-1) + fib(n-2)
Collatz function could be written this way too: function collatz(n, total = 0) { if (n == 1) { return total; } else if (n % 2 == 0) { return collatz(n / 2, (total += 1)); } else { return collatz(3 * n + 1, (total += 1)); } } But I think the one in the video I think is more elegant.
Amazing explanation to such a abstract topic!. I shortened it a little more function factorial(n){ return n==1 ? 1 : n* factorial(n-1); } console.log(factorial(5)); //120
This was MIND BLOWING. Happy I got to make the function work, but needed DDB to point me to the solution of "return + 1", would have never EVER figured that one out, although once explained makes much sense. Thank you for a terrific short, very helpful :)
Thank you so much for posting this Vid! I'm currently taking Data Structures at another University and this video made the concept easier to understand than my professor's lecture!
Way to make me feel dumb for not learning the Fibonacci sequence in Elementary school and waiting until I was a dumb teenager getting into Tool to learn about it
About the collatz conjucture, the recursive cases have the return + 1. I tested with the + 1 and without the tests, there are same results. I'm curious to see your point of view on putting the +1 in those recursive cases. Before checking your answer, I put the return -1 in the end of the code to avoid the return error and -1 will disprove the conjecture (which is impossible). And, thank you for making this video!
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
for mine, i initialized int i = 0 as a global variable. my collatz function had three if statement for the three different possibilities. then created a counter in my collatz function that would i++ every time the collatz function called itself. then returned total i after n == 1 and printed it.
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
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.
My solution in Python :) def collatz_conjecture(n, step=0): if n == 1: return step else: # n % 2 return 0 for even, not 0 = 1 (Truthy Value) if not n % 2: return collatz_conjecture(n/2, step+1) if n % 2: return collatz_conjecture(3*n+1, step+1) print("Steps: ", collatz_conjecture(7))
I did the Collatz one like this instead, for me it was easier to understand: function collatz(number, steps = 0){ if(number === 1){ return steps; } if(number % 2 === 0){ return collatz(number/2, steps + 1); } else{ return collatz(3*number + 1, steps + 1); } }
(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.
Full code Factorial problem #include #include int factorialFunction(int n); int main(void) { //to creation a function that calls itself int n = get_int("choose a number buddy: " ); int productSum = factorialFunction(n); printf("yes this worked! %i", productSum); } int factorialFunction(int n) { int sum = 0; // base case if (n == 1) { return 1; } else { sum = n * factorialFunction(n - 1); } return sum; }
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); }
10:57 there's a typo - 'is applies' should read 'is applied' Also, why are we multiplying by 3 and then adding 1? Just add 1...it does exactly the same thing with less steps
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
If the collatz function eventually returns 0 to mean true/done with an iteration and we add +1 to act as a counter, why isn't that just built into the function? What use case would returning 0 have?
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.
My code looks more redundant than this. but where in this code is it returning the number of steps it took to get to 1? and if i want to print out that number?
Just to help people out since this took me a while since he is assuming you know he is calling a function collatz. Basically I am just showing you need to have an int main(void) that calls the Collatz. This video also helps which is from week 4 ua-cam.com/video/aCPkszeKRa4/v-deo.html #include #include int collatz(int n); int main(void) { printf("%i ", collatz(15)); } int collatz(int n) { // base case if (n == 1) { return 0; } else if ((n % 2) == 0) { return 1 + collatz(n/2); } else { return 1 + collatz(3*n + 1); } }
I tried writing a collatz conjecture using recursion and mine looks VEEERY different to his. I just wonder what the logic of 1 + function() is? It doesn't seem to be adding one to the value of the outputted return value from that function?? Is it more like a... if n is initially 5 (which means 5 steps, using collatz conjecture, to 1) (1 +) collatz(n) + (1 +) collatz(n) + (1 +) collatz(n) + (1 +) collatz(n) + (1 +) collatz(n) Is it more like that above? if that even makes sense. Because I was pretty sure you couldn't return multiple values in functions unless you use pointers... or structs/arrays (apparently the latter are possible according to a website I just checked). So is the above more like returning (1 +) ____ (1+) ____ (1+)____ (1+) _____ (1+) (1+1+1+1+1) to the function before it finally returns the sum of that to be printed? Hope this made sense lol (and yes I am using the youtube comment sections as a way to have a conversation lol)
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.
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).
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 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
Full code Collatz problem #include #include int collatzConjecture(int n); int main(void) { //to creation a function that calls itself int n = get_int("choose a number buddy: " ); int collatzReturn = collatzConjecture(n); printf("the collatz return was %i ", collatzReturn); } int collatzConjecture(int n) { int turns; if (n == 1) { return 0; } else if(n % 2 == 0) { turns = 1 + collatzConjecture(n/2); } else { turns = 1 + collatzConjecture(3*n + 1); } return turns; }
I don't understand the Fibonacci, you said the fourth element would be 2: (n-1)th element + (n-2)th element, Where do you get the N value from? And why are you adding the second and third element and not 1st as 2nd?
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?
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.
@@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)
Could anyone explain to me why the two recursive statements for the final solution have "return 1 +" at the beginning? I'm just trying to get my head around the logic of it
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.
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)).
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. 😬
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!
Thanks Doug! Nice talk as usual. Just curious, for the Collatz function, may I use "break" in the first condition (if n == 1), or, there is not actually such use in C? In my code, I used break for "if n==1" and I added a "return 0" after "else".. I am new in C by the way.
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
The last example for collatz . how he calculated no. of steps , what i understood he made recursion to let the number be 1 , and didn't calculate the steps , Am i right ? or something i miss understood it
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.
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.
i was trying to keep it simple and run it with get_int and printf but i keep getting error: function definition is not allowed here its at the first "{" after I started int collatz (n) any thoughts?
@@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); } }
Recursion: *exists*
Me: uhhh..that's sort of cool
Doug: SEXAYYY!!!
you calling those lines of code sexy just made my day
7:33 I pity the fool who only watches the main lecture (even though those are great) because they'll miss gems like this. And Doug's a damn good teacher.
so you're telling me there are people who can solve psets with only main lecture?
7:33 True programmer love. :D You're the best, Doug.
When he described recursion as sexy I almost spat out my breakfast LOOOL.
sexayyy 😅
he just called a few lines of code sexy.... that's when u know ur talkin to about a real programmer.
lolllll
It is tho
You are transforming the life of a class of 15 people in Brazil, doug! Thank you so much Malan and Doug!
Parabéns amigo
Parabéns amigo
shoutout my boy Bryan one time
Encontrei um brasileiro🇧🇷
I took CS50X couple of years ago. I didn't finish, but it taught me more about programming than anything else.
Jan Negrey why don't u complete then?
@@jayant9151 that's what I asked myself recursively
@@KillTheAlarm69 what's your base condition?
Find you a man who talks about you the way Doug talks about recursion
underrated
Literally
I Love the little finger tap he does on 7:33 LoL
Paused the video cause I didnt want to disapoint doug !
I paused the video and tried to do by myself, but I don't get the final example.
"You may recall from elementary school days" lol Doug no one learned about Fibonacci in elementary
Doug did :D
@@kattodoggo3868 doug was born in harvard
We did in the UK.
This video just made recursive algorithms very sound interesting and easy to follow
Watching this, i find myself constantly saying, "This is amazing". Thanks Doug.
2:15 "couple of facts, pun intended" damn Dough, you're funny too.
Jesus this was high quality and explained super well with easy concepts, I went through a bunch of tutorials that used complex terms etc... looking at u hackerrank...
but thanks CS50 and Doug
7:05 everything in lecture that confused me clicked. Thanks Doug~!
If anyone else was confused during the fib sequence part when he says if n == 0 return 1, elsif n == 2 return 1
Base cases should be if n == 0 return 0, elsif n == 1 return 1, else fib(n-1) + fib(n-2)
Collatz function could be written this way too:
function collatz(n, total = 0) {
if (n == 1) {
return total;
} else if (n % 2 == 0) {
return collatz(n / 2, (total += 1));
} else {
return collatz(3 * n + 1, (total += 1));
}
}
But I think the one in the video I think is more elegant.
this was also my solution
I didn't expect it to be that easy. Thanks for the explanation, really. Good luck, guys, and don't give up.
Amazing explanation to such a abstract topic!. I shortened it a little more
function factorial(n){
return n==1 ? 1 : n* factorial(n-1);
}
console.log(factorial(5)); //120
Opened it here from CS50 official website just to praise the passion of the tutor! Indeed, programming is sexy!
This was MIND BLOWING. Happy I got to make the function work, but needed DDB to point me to the solution of "return + 1", would have never EVER figured that one out, although once explained makes much sense. Thank you for a terrific short, very helpful :)
i solved the last exercise correctly but in slightly different way :
function Colatz(number, steps=0){
if(number
Thank you so much for posting this Vid! I'm currently taking Data Structures at another University and this video made the concept easier to understand than my professor's lecture!
No one:
Doug: So here there's a couple of facts... Pun intended
Me: HAHAHAHA
this man beating his meat to lines of code fr, true programmer, real G
He's a certified hood gangsta
@@LagrangePoint0 like no others
@@edoardodepiccoli3004 He's even throwing his gang's signs at 7:14
This guy's been coding for so long that it now turns him on
Way to make me feel dumb for not learning the Fibonacci sequence in Elementary school and waiting until I was a dumb teenager getting into Tool to learn about it
bro said the code is sexy
About the collatz conjucture, the recursive cases have the return + 1. I tested with the + 1 and without the tests, there are same results. I'm curious to see your point of view on putting the +1 in those recursive cases. Before checking your answer, I put the return -1 in the end of the code to avoid the return error and -1 will disprove the conjecture (which is impossible). And, thank you for making this video!
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
for mine, i initialized int i = 0 as a global variable. my collatz function had three if statement for the three different possibilities. then created a counter in my collatz function that would i++ every time the collatz function called itself. then returned total i after n == 1 and printed it.
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
I get this. But I find recursion very hard to implement in my code. I always just want to iterate.
Doug Lloyd, the mind-blower!
The "Call Stacks" short includes an extremely delighting visualization on this, see 3:20 in ua-cam.com/video/aCPkszeKRa4/v-deo.html
Thanks! This helped a lot!
Can anyone explain me,in a very "coding for dummies way", why in the collatz recursion the return value is RETURN 1 + collatz?
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: ua-cam.com/video/aCPkszeKRa4/v-deo.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.
Now it all make sense I've raking my brain on this. Thank you!!
He's Doug Lloyd! This is CS50!)) Thanks Doug!
4 lines of code looking extra dapper lol. I LOLED at kind of sexy. Great explaination!
My solution in Python :)
def collatz_conjecture(n, step=0):
if n == 1:
return step
else:
# n % 2 return 0 for even, not 0 = 1 (Truthy Value)
if not n % 2:
return collatz_conjecture(n/2, step+1)
if n % 2:
return collatz_conjecture(3*n+1, step+1)
print("Steps: ", collatz_conjecture(7))
I did the Collatz one like this instead, for me it was easier to understand:
function collatz(number, steps = 0){
if(number === 1){
return steps;
}
if(number % 2 === 0){
return collatz(number/2, steps + 1);
}
else{
return collatz(3*number + 1, steps + 1);
}
}
That's exactly the way I solved it before seeing his answer.
CS50 is an overall sexy course!
can anyone tell why the heck he adds 1 to collatz(n/2) or collatz(3n+1) ?
thanks in advance :)
+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.
Tideman smiling at you
Full code Factorial problem
#include
#include
int factorialFunction(int n);
int main(void)
{
//to creation a function that calls itself
int n = get_int("choose a number buddy: " );
int productSum = factorialFunction(n);
printf("yes this worked! %i", productSum);
}
int factorialFunction(int n)
{
int sum = 0;
// base case
if (n == 1)
{
return 1;
}
else
{
sum = n * factorialFunction(n - 1);
}
return sum;
}
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);
}
This was a very good explanation. Thank you.
7:33
THIS IS CS50!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
10:57 there's a typo - 'is applies' should read 'is applied'
Also, why are we multiplying by 3 and then adding 1? Just add 1...it does exactly the same thing with less steps
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
"Yes this is indeed sexy" (me looking at my Collatz function)
7:32 Real Programmer
Thank you, this really helped. It is greatly appreciated!
This is incredibly helpful. Thank you!
If the collatz function eventually returns 0 to mean true/done with an iteration and we add +1 to act as a counter, why isn't that just built into the function? What use case would returning 0 have?
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 cornfused, have to watch this again
It clicked right at the end. I didn't call the function each time, I just ran either n/2 and didn't return anything.
My head is about to explode.
My code looks more redundant than this. but where in this code is it returning the number of steps it took to get to 1? and if i want to print out that number?
Just to help people out since this took me a while since he is assuming you know he is calling a function collatz. Basically I am just showing you need to have an int main(void) that calls the Collatz. This video also helps which is from week 4 ua-cam.com/video/aCPkszeKRa4/v-deo.html
#include
#include
int collatz(int n);
int main(void)
{
printf("%i
", collatz(15));
}
int collatz(int n)
{
// base case
if (n == 1)
{
return 0;
}
else if ((n % 2) == 0)
{
return 1 + collatz(n/2);
}
else
{
return 1 + collatz(3*n + 1);
}
}
You can do collatz(n) in a simple while loop without polluting the stack.
yes but that's not really the point is it
Doug sos un campeon!
I tried writing a collatz conjecture using recursion and mine looks VEEERY different to his. I just wonder what the logic of 1 + function() is? It doesn't seem to be adding one to the value of the outputted return value from that function?? Is it more like a... if n is initially 5 (which means 5 steps, using collatz conjecture, to 1)
(1 +) collatz(n) + (1 +) collatz(n) + (1 +) collatz(n) + (1 +) collatz(n) + (1 +) collatz(n)
Is it more like that above? if that even makes sense. Because I was pretty sure you couldn't return multiple values in functions unless you use pointers... or structs/arrays (apparently the latter are possible according to a website I just checked). So is the above more like returning (1 +) ____ (1+) ____ (1+)____ (1+) _____ (1+)
(1+1+1+1+1)
to the function before it finally returns the sum of that to be printed? Hope this made sense lol (and yes I am using the youtube comment sections as a way to have a conversation lol)
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.
beautifully explained. Thank you!!
Neither the program I wrote worked for 0, nor the one shown here. I can see why, but how to solve it without giving it an else if condition?
Another way to write the body of fact(): n == 1 ? 1 : n * fact(n - 1)
I love you Doug!
I think this code has mistake
what if it is 0!
i think it should be 1, but in this video hw didn't mentiones that
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.
A coding poet!...💖
Me too. I don't quite get why we have to return 1 with the Collatz conjecture.
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
Full code Collatz problem
#include
#include
int collatzConjecture(int n);
int main(void)
{
//to creation a function that calls itself
int n = get_int("choose a number buddy: " );
int collatzReturn = collatzConjecture(n);
printf("the collatz return was %i
", collatzReturn);
}
int collatzConjecture(int n)
{
int turns;
if (n == 1)
{
return 0;
}
else if(n % 2 == 0)
{
turns = 1 + collatzConjecture(n/2);
}
else
{
turns = 1 + collatzConjecture(3*n + 1);
}
return turns;
}
thank you so much you just help me with a question
I don't understand the Fibonacci, you said the fourth element would be 2: (n-1)th element + (n-2)th element,
Where do you get the N value from? And why are you adding the second and third element and not 1st as 2nd?
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?
Hello from The Odin Project.
function collatz(n) { console.log(n);
n==1?n:n%2==0?collatz(n/2) :collatz(3*n+1);
} guys from odin hai
13:00 if you keep returning 1 over and over again, will it sum them up automatically?
No because then you aren't using that return value in any way and always getting 1
He's so dreamy :3
so chubby ^^
@@LagrangePoint0 Yeah, you get it.
i don't understand the meaning of "1 + " in the return statement. can someone explain?
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
Thanks a lot.
Could anyone explain to me why the two recursive statements for the final solution have "return 1 +" at the beginning? I'm just trying to get my head around the logic of it
see call stacks: ua-cam.com/video/aCPkszeKRa4/v-deo.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 + ... ?
Can we use loops in Recursive functions? if we can; what makes recursive programming different from interactive. programming
ill be honest. I came to this video just for the comments
Hello The Odin Project students :)
Thanks, Doug. Very helpful.
Hello from TheOdinProject Student👋
hi bro keep going
Ok Doug. For you
miss you dougie !!!
Doug is bae.
The code will not work if to write this for odds: else if (n % 2 != 0) ... Why?
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.
good explanation!
Awesome
for odd number why can't you just use n+1 instead of 3n+1? I don't see why multiplying by 3 is necessary
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
Thanks Doug! Nice talk as usual. Just curious, for the Collatz function, may I use "break" in the first condition (if n == 1), or, there is not actually such use in C? In my code, I used break for "if n==1" and I added a "return 0" after "else".. I am new in C by the way.
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!
The last example for collatz . how he calculated no. of steps , what i understood he made recursion to let the number be 1 , and didn't calculate the steps , Am i right ? or something i miss understood it
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.
Pretty good video
Int collatz(int n){
if (n == 1){
return 1;
}
Else if ( n % 2 == 0)
{
return collatz(n)/2;
}
Else
{
return 3 * collatz(n) +1;
}
}
can someone explain,
This is the error msg when I run this
"non-void function does not return a value in all control paths [-Werror,-Wreturn-type]"
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.
Very nice..
Are you looking for recursion?
Are you looking for recursion?
@@juliangallego7963 Are you looking for recursion?
@@gona3665 Are you looking for recursion?
@@Drakonus_ Are you looking for recursion?
omg saw a whole nother side of doug once he called it sexy
i was trying to keep it simple and run it with get_int and printf but i keep getting
error: function definition is not allowed here
its at the first "{" after I started int collatz (n)
any thoughts?
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 !
7:25 ummm... ok. i mean the society accepts all sexualities now right?
👏👏👏
I also recommend watch this video: ua-cam.com/video/aCPkszeKRa4/v-deo.html (clear explanation using stack )