I guess you save on space.. I dont know.. I am software developer and even I dont know haha

mojaboy · Oct 6, 2015 9:41 AM

cp21, First: Your question should have been "Why is recursion an important technique in programming?". Recursion is not something that only relates to c++ or c. It is a concept that can be implemented in most procedural languages. It is not just a native idea to c++. Second: Why do you need recursion? ==>when you are programming you have to find some results. So you write a function to do that. but then once you realize that those results are not exactly what you want and maybe you need to run them through the same function again to refine them. Would you want to write the same function again? Lets say you wrote the same function the second time, but your results are still not refined, meaning that you are getting closer to the absolute result but you are not there yet. so how many times are you going to keep doing that? you never know!, it depends on what you are trying to do and what your scale is. Therefore, recursion becomes absolutely crucial especially if you are writing anything mathematical. So this is how recursion works: there is a base case/there are base cases which is waiting to be satisfied. so you evaluate some results and then you call the same function again only this time you plug in the results as arguments, and you keep doing that while the base case/cases is not satisfied. once the base case hits, recursion terminates and that is your answer! it's hard to explain without showing you some code. So i will try to explain a simple recursion program that involves fibonacci numbers. First here is what the fibonacci sequence looks like: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34.......inf Notice that each number is the sum of the previous two numbers in this sequence. i.e 34 = 21 + 13, 21 = 13 + 8 and so forth and that 0 and 1 are given to you as base cases where 0th fibonacci number is 0 and the 1st fibonacci number is 1 """ KB Oct 6, 2015 Demonstration of recursion : a case of fibonacci numbers for cp21 """ def fibonacci(number): if number == 0: # This is one of the base cases return 0 elif number == 1: # This is your another base case return 1 else: return fibonacci(number-1) + fibonacci(number-2) # function calling itself # Now call the function to get the 20th fibonacci number a = fibonacci(20) print(a) # This gives you a = 6765, that means the 20th fibonacci number is 6765 So how does it actually work? you asked the function to find you the 20th fibonacci number. Now, it checks is 20 == 1? no, is 20 == 0? no both base cases have failed so it goes to the recursive part and does this: find fibonacci(20-1) + fibonacci(20-2) = fibonacci(19) + fibonacci(18) But remember, the function does not know what fibonacci(19) or fibonacci(18) is so it checks again is 19 == 1? no is 19 == 0? no both base cases fail. now it does the recursive part and says okay let me find fib(19-1) + fib(19-2) = fib(18) + fib(17) but it does not know those. so it keeps decreasing by 1 and 2 each time until it hits the base case where fib(1) == 1, or fib(0) = 0. Then finally once it knows what fib(0) and fib(1) are, it can find fib(2) and then it uses that value to find f(3) and that to find fib(4) ... all the way to fib(20). So in this case it went backwards from 20 to 1 in terms of function calls and once it got the results, the function went forward again from 0 and 1 to 20 with the real values.and gave you what you asked for. Note: If you change the number to 100 or a 1000, you will start frying your computer depending on how powerful it is. The stack fills quickly with each call. Keep that in mind! Also, Keep in mind that this is a very primitive example of recursion. Very very complicated and much powerful things can be achieved using recursion. if you want to see examples of complicated recursion stuff and how it works i could show you my ray tracing program. Your mind will be blown. ================================ To mojaboy: By "Save on space" if you mean the size(length) of your code, then you are right in general. But if you are talking about the memory space, you are wrong. Infact when you run things recursively, the stack builds up and the "memory" fills quickly. Take a simple example of recursion say finding fibonacci numbers, or find factorial. If you plug in a large number, you will possibly get a stack overflow. So recursion does not necessarily save space in that sense. Last edited: 06-Oct-15 10:45 PM

kb3292 · Oct 6, 2015 10:42 PM