deldalton Posted April 23, 2013 Share Posted April 23, 2013 (edited) I'm trying to learn Javascript and I've just briefly read about recursion in functions. I've been given the following task. Consider this puzzle: By starting from the number 1 and repeatedly adding 5 or multiplying by 3, an infinite amount of new numbers can be produced. How would you write a function that, given a number, tries to find a sequence of additions and multiplications that produce that number? For example, the number 13 could be reached by first multiplying 1 by 3, and then adding 5 twice. The number 15 can not be reached at all. Here is the solution: function findSequence(goal) { function find(start, history) { if (start == goal) return history; else if (start > goal) return null; else return find(start + 5, "(" + history + " + 5)") || find(start * 3, "(" + history + " * 3)"); } return find(1, "1");} print(findSequence(24)); If this code is run the following is printed to the console: (((1 * 3) + 5) * 3) In my head, the code is processed in the following steps. 1. findSequence is called, with a parameter value of 24.2. findSequence calls find giving the first parameter a value of 1 and the second parameter a value of "1".3. The find function looks to see if the start parameter value is equal to the value of the goal parameter.4. As the start parameter value, in this particular case, is not equal to the value of the goal parameter, check to see if the start parameter value is larger than the goal parameter value.5. As the start parameter value, in this particular case, is not equal to the value of the goal parameter, return one of the following statements:find(start + 5, "(" + history " + 5)")orfind(start * 3, "(" + history + " * 3)" However, this is then where I become stuck. I can't quite understand the statements it's trying to then run. I can see that find(start + 5, changes the value of history to 5. Then "(" + history + " + 5)") . This to me would print (1 + 5 ( + 5) + 5)). Similarly I see the other statment printing as (1 * 3 ( + 3) * 3)). I just can't quite grasp what I'm missing. I suspect it's something obvious and really simple but it would be great if someone could provide me with the missing pieces. I appreciate that there is most likely an alternative way of coming to the same result. However, I'd like to fully understand what is being shown to me here before I move on. Many thanks. Edited April 23, 2013 by deldalton Link to comment Share on other sites More sharing options...
jeffman Posted April 23, 2013 Share Posted April 23, 2013 You will find it very instructive to print or alert the value of history at the beginning of the find function. Notice what happens when the value of start exceeds the value of goal. What you will find is that your suspicions are correct, but that you have not followed them to their conclusion. Link to comment Share on other sites More sharing options...
davej Posted April 23, 2013 Share Posted April 23, 2013 (edited) That seems to be a particularly nasty example. I'm not an expert coder but I would hate to deal with it. I put it into this form: <!DOCTYPE html><html><head><title>recursive mess</title><script>window.onload = function() {document.getElementById('btn').onclick=calculate; function findSequence(goal) { var out = document.getElementById('out'); out.innerHTML=""; function find(start, history) { out.innerHTML += "start=[" + start +"]<br/>"; out.innerHTML += "history=[" + history +"]<br/>"; if (start == goal) { out.innerHTML += "start == goal => success!<br/>"; return history; } else if (start > goal) { out.innerHTML += "start > goal => dead end!<br/>"; return null; } else { out.innerHTML += "start < goal => continue with start="+(start+5)+" and start="+(start*3)+"<br/><hr/>"; return find(start + 5, "(" + history + " + 5)") || find(start * 3, "(" + history + " * 3)"); } } return find(1, "1");} function calculate(){var inp = document.getElementById('in');var result = document.getElementById('result');var goal = Number(inp.value); result.innerHTML = "["+ findSequence(goal) +"]";} }//end of onload</script> </head> <body> <p>Input:</p> <input type="text" id="in" value="24"/><input type="button" id="btn" value="Run"/> <p>Process:</p> <div id="out"></div> <p>Result:</p> <div id="result"></div> </body></html> A more conventional example of recursion would be something simple like converting a number from decimal to binary. There is a predictable endpoint. At that endpoint the recursion "unwinds" and provides the answer. http://cgi.csc.liv.a.../recursion.html Edited April 23, 2013 by davej Link to comment Share on other sites More sharing options...
justsomeguy Posted April 23, 2013 Share Posted April 23, 2013 Note that when you do this: find(start + 5, "(" + history + " + 5)") it does not change the current values of start or history, it calls a new copy of the function with new values for those parameters. Link to comment Share on other sites More sharing options...
deldalton Posted April 24, 2013 Author Share Posted April 24, 2013 Thank you for your suggestions and input. I think that what I'm struggling to understand is how/where the loop stores the values it finds and then how it calls them in the next cycle of the if loop. Because I can't see how the start and history values are produced in the next cycle I can't see how it completes. I really hope that makes sense. Deirdre's Dad. Your alert/print suggestion was brilliant. Although I'm still stuck at this point, it's clear that seeing the found values during each cycle of the loop will help me understand what is happening. davej. I will have a read through the explaination you provided in the link. Thank you. justsomeguy. Thanks for pointing out that the values of start and history are not actually changed but that a new copy of the function is created with new values. This, I think, is the part I'm stuck on. I can't see what the new values are or how they're applied to be used the next time "find" is called. Link to comment Share on other sites More sharing options...
deldalton Posted April 24, 2013 Author Share Posted April 24, 2013 He's another example I'm looking into to help me understand recursion. function factorial(n) { // Termination condition to prevent infinite recursion if (n < 0) { console.log("Can't make a factorial from a negative number."); return; } // Base case if (n === 0) { return 1; } // Recursive case return n * factorial(n - 1);}factorial(6); So, in this particular example, when factorial(6) is called this, at least in my mind, is what happens. 1. Check to see if n (6) is less than 0. 6 is not less than 0 so skip code within braces and move on to next line of code.2. Check to see if n (6) is equal to 0. 6 is not equal to 0 so skip code within braces and move on to the next line of code.3. Return the value of n * factorial(n - 1). Or, n * factorial(5). So, 6 * 5 which is 30. 3.1. Check to see if n, which in this new instance is equal to 5, is less than 0. 5 is not less than 0 so skip code within braces and move on to the next line of code. 3.2. Check to see if n, which in this new instance is equal to 5, is equal to 0. 5 is not equal to 0 so skip code within braces and move on to the next line of code. 3.3. Return the value of n * factorial(n - 1). Or, n * factorial(4). So, 5 *4 which is 20. Now, I won't continue any further, because I already know this is incorrect and I'm missing something. I know that at 3.3 it should, in fact, multiply 30 by 4. But, I don't understand where the value 30 (which is calculated at step 3.) is stored for it to be "called" in 3.3. Link to comment Share on other sites More sharing options...
jeffman Posted April 24, 2013 Share Posted April 24, 2013 3. Return the value of n * factorial(n - 1). Or, n * factorial(5). So, 6 * 5 which is 30.That's your misunderstanding. factorial(5) is the last value returned, not the first. That is because factorial(5) calls factorial(4), which calls factorial(3), and so on. The smallest numbers get multiplied first and work their way backward to 6. That's the tricky thing about recursion. Link to comment Share on other sites More sharing options...
deldalton Posted April 24, 2013 Author Share Posted April 24, 2013 That's your misunderstanding. factorial(5) is the last value returned, not the first. That is because factorial(5) calls factorial(4), which calls factorial(3), and so on. The smallest numbers get multiplied first and work their way backward to 6. That's the tricky thing about recursion. I've found and read through an article that shows, through the use of diagrams, how Javascript interprets the code. I would link to the article but I'm uncertain if it's allowed, as it does mention another website that is also dedicated to teaching web coding etc. Now, the maths I understand. And the diagram explains what it's doing. I think my problem is simply that I haven't seen enough examples and that the examples aren't applied to a task that, of yet, seems useful. Link to comment Share on other sites More sharing options...
deldalton Posted April 24, 2013 Author Share Posted April 24, 2013 So, perhaps, my question should be re-written ... Can anyone provide a "real-life" application for the recursive function? Link to comment Share on other sites More sharing options...
davej Posted April 24, 2013 Share Posted April 24, 2013 One aspect of your first example that is worth noting is that only one solution can be found. For "string1"||"string2" the result will always be string1 if string1 is not null. Also for func1()||func2() the func2() will never be executed unless func1() is null. The factorial is a classic example of recursion, but I honestly don't know where recursion is used as a practical solution. It might be practical for something like the traveling salesman problem. Link to comment Share on other sites More sharing options...
justsomeguy Posted April 24, 2013 Share Posted April 24, 2013 The factorial is a fine example, a factorial calculation does get used (although mostly by math people). To understand how recursion works you need to understand the call stack. The stack is a list of contexts that code gets executed in. If you're familiar with scoping (e.g. global variables versus local variables), that's part of the stack. Each context of the stack is a scope with its own variables defined. Each time the function calls itself it adds another context to the stack. As the functions finish the recursion backs out of the stack until it's back in the context which originally called the function. So each time you call the function it adds another context to the stack, and each time a function returns a context gets removed from the stack and execution resumes in the context below it. When you call factorial(6) from the global scope, one context is added to the stack for factorial(6), which calls factorial(5) and adds a context for that, which calls factorial(4) and adds a context, etc. That original call to factorial(6) is waiting for the recursive call to return its value before it can return the value for 6 * factorial(5). So the context doesn't go away, it's waiting for the context that it called to finish before itself can finish. So the recursion causes several contexts to get added to the stack, all the way until recursion stops (when n = 0), and then once recursion stops the execution backs out of each context as they return their values until it gets back to the global context where you called factorial(6). So the stack might look something like this: Global contextcall factorial(6) n = 6 call factorial(5) n = 5 call factorial(4) n = 4 call factorial(3) n = 3 call factorial(2) n = 2 call factorial(1) n = 1 call factorial(0) n = 0 return 1 (return = 1) return 1 * 1 (return = 1) return 2 * 1 (return = 2) return 3 * 2 (return = 6) return 4 * 6 (return = 24) return 5 * 24 (return = 120) return 6 * 120 (return = 720)factorial(6) = 720 So you can see that the stack gets all of these contexts added to it, and at the end once they start returning values everything backs out again until you get back to where you started. Another common use for recursion is if you're printing a tree structure, like a directory structure. If you want to write a PHP script to list the contents of a directory, including all subdirectories, then the function would open the target directory, first get a list of all child directories and call itself to list the contents of those (assuming you want directories listed before files), and then list the files. It would look something like this: function list_dir_recursive($dir_name, $indent = 0){ // print the directory name first, with an indent for ($i = 0; $i < $indent; $i++) { echo '..'; // indent } echo $dir_name . "<br>"; $directories = array(); $files = array(); // get a list of the directory contents $list = scandir($dir_name); foreach ($list as $item) { // avoid infinite recursion if ($item != '.' && $item != '..') { // if the item is a directory if (is_dir($dir_name . DIRECTORY_SEPARATOR . $item)) { // add to the list of directories $directories[] = $item; } else { // add to the list of files $files[] = $item; } } } // print directories first foreach ($directories as $dir) { // list the contents of this directory, with a larger indent list_dir_recursive($dir_name . DIRECTORY_SEPARATOR . $dir, $indent + 1); } //then print files foreach ($files as $file) { for ($i = 0; $i < $indent; $i++) { echo '..'; // indent } echo $file . "<br>"; }} In that example the function doesn't return anything, it just prints data. It prints the name of the directory you told it to list, then the subdirectories (plus their contents, through recursion), then the files. 2 Link to comment Share on other sites More sharing options...
deldalton Posted April 25, 2013 Author Share Posted April 25, 2013 justsomeguy. Thank you for the explanation and examples. I had already come across these exact explanations and examples, shortly before reading your post, which definitely helps explain what's meant to happen and how you can apply a recursive function. I only wish the many articles I had read previously had used your post! I appreciate that I have an understanding of it now but it is actually fairly simple. The problem, I think, is the lack of resources explaining it so simply. Link to comment Share on other sites More sharing options...
Recommended Posts
Create an account or sign in to comment
You need to be a member in order to leave a comment
Create an account
Sign up for a new account in our community. It's easy!
Register a new accountSign in
Already have an account? Sign in here.
Sign In Now