Hi guys, I'm not understanding the recursive very well, I guess that my approach to solve by recursive is totally wrong !
do I understand what's the recursive is?! Yup, how can I prove that? Yup here I will show you, in everytime I want to solve by recursive way what I'm doing is: visualizing there's a stack and in every call of my function as it's recursive I slice the stack into "window" etc... till the final call finish his "operation" .. what do I mean with final call?! meaning until I arrive the STOP conditions ! ...it takes me alot of time for solving a problem in a recursive way although it would be solved in a short time !
May anyone help me how can I think as recursively way to solve in a short time? what approach should I go with?
if there's any analogues about Recursion that can boost me to solve problems in a short time and not following every step on the recursion to see if it's giving me true answer or not !


thanks in advance and I appreciate you guys for your cooperative !

 

Hi guys, I'm not understanding the recursive very well, I guess that my approach to solve by recursive is totally wrong !
do I understand what's the recursive is?! Yup, how can I prove that? Yup here I will show you, in everytime I want to solve by recursive way what I'm doing is: visualizing there's a stack and in every call of my function as it's recursive I slice the stack into "window" etc... till the final call finish his "operation" .. what do I mean with final call?! meaning until I arrive the STOP conditions ! ...it takes me alot of time for solving a problem in a recursive way although it would be solved in a short time !
May anyone help me how can I think as recursively way to solve in a short time? what approach should I go with?
if there's any analogues about Recursion that can boost me to solve problems in a short time and not following every step on the recursion to see if it's giving me true answer or not !


thanks in advance and I appreciate you guys for your cooperative !

Since you posted in Programming, I suppose you are trying to develop the proper code to perform ... something. Can you provide an example of exactly what you mean? I'm quite familiar with iterative solutions to solve mathematical problems that have no analytical solution. But you're probably doing something else. Please elaborate.

It's possible that other folks here already understand exactly what you've described. Not me.

 

lets say I want to do Fibonacci sets in recursive way .. how should I think to write the code of that recursion? which approach to take for thinking in a good way to build the recursion of fibonacci without getting stuck inside the iterations of the "recursion" itself

 

lets say I want to do Fibonacci sets in recursive way .. how should I think to write the code of that recursion? which approach to take for thinking in a good way to build the recursion of fibonacci without getting stuck inside the iterations of the "recursion" itself

Well OK, some background here.
https://en.wikipedia.org/wiki/Fibonacci_number

What is the input and the desired output of your program?

edit - Know what? I just read this
https://en.wikipedia.org/wiki/Recursion_(computer_science)
to get a better idea of what you are asking and realize it's out of my experience. Never did such a thing. Sorry.

 

May anyone help me how can I think as recursively way to solve in a short time? what approach should I go with?
if there's any analogues about Recursion that can boost me to solve problems in a short time and not following every step on the recursion to see if it's giving me true answer or not !

As you seem to understand, a recursive solution solves a problem by repeatedly transforming it into a smaller sub-problem until a base case is reached, where the problem is as simple as it can be. It then recombines the results of solving the sub-problems, which ends up being the solution to the bigger problem.

So, the big idea with recursion is simplification: each recursive call should work on a smaller/simpler problem. As humans don't usually think recursively, it's rarely obvious how to do this. But there are certain patterns that recursive algorithms tend to use, and once you get to know them you won't have to think through each step of the recursion.

For example, say you were asked to write a function f that accepts a positive integer and returns the sum of the digits in that integer, e.g., f(2076) = 15 because 2 + 0 + 7 + 6 = 15. How can we solve this recursively? Here's one implementation:

unsigned int f(unsigned int n) {
  if ( n == 0 ) return 0; // base case

  return n % 10 + f(n / 10);
}

All the work is being done in line 4. The expression n % 10 gives us the last digit of the number n, e.g., 567 % 10 = 7. The expression n / 10 is an integer division, so it discards the last digit (the one we just picked out with n % 10); in this way, we provide a simpler/smaller number to the next recursion. Once the given number becomes smaller than 10, the result of the division is 0, which takes us to our base case. Then, the whole thing unwinds, summing up the n % 10 numbers that were left on the stack.

Here's an example of what it looks like using n = 567:

567 % 10 + f(567 / 10)     ->  7 + f(56)
    56 % 10 + f(56 / 10)   ->  6 + f(5)
        5 % 10 + f(5 / 10) ->  5 + f(0)
            return 0       ->  0 + 5 + 6 + 7 = 18

The key to avoiding having to think through each recursion level is to recognize the pattern. Here's another example with the same type of pattern; try to guess what it does:

unsigned int g(unsigned int n) {
  if ( n == 0 ) return 0; // base case

  if ( n == 7 )
    return 1 + g(n / 10);
  else
    return g(n / 10);
}

Hopefully you can see that it counts how many 7s there are in the number n, e.g., g(2737) will return 2. Search and read through examples of recursive solutions and you'll start to recognize a handful of patterns. Once you can spot them, most college-type recursion problems will become much easier to solve.

 

Maybe I didn't elaborate as much on my question;
my question is whenever I want to solve a problem in recursive way, what approach should I think with to start building my code in recursively way? to demonstrate more, I'm always starting with stop condition and I stuck there don't know how to complete with recursive way of thinking ! so when I build my code, I build my stop condition for recursive to be stop off, but afterwards I feel like I'm lost and can't complete the code in recursive way ..although my first step on stop conditions I've already written it.

what I'm looking for like something that I can depend on and once I stuck in stop conditions of recursive then can help me to get out and continue my code in recursive manner ...

 

There isn't any "something that I can depend on" when it comes to things like this. You need to understand the underlying concepts and then learn how to apply them to specific problems via lots of practice.

For most recursive problems, you need to identify two things -- the base case (or cases) and the recursive case.

Take your Fibonacci numbers as an example. What is the definition of the nth Fibonacci number? Simple, it's the sum of the prior two Fibonacci numbers.

So there's your recursive case.

Fib(n) = Fib(n-1) + Fib(n-2)

What's the base case? Here the first one that we can calculate directly is Fib(2), since for that we need Fib(1) and Fib(0). We can't compute Fib(1) recursively since we would need Fib(-1) which is undefined. So we have TWO base cases:

Fib(0) = 0
Fib(1) = 1

Notice that this can be simplified to

if (n < 2) then Fib(n) = n

So the pseudocode for your recursive implementation becomes very simply

Fib(n)
if (n < 2)
   return n
return Fib(n-1) + Fib(n-2)

I generally find that nailing down the recursive case is pretty easy and that then helps me see more clearly what the base case needs to be.

 

There isn't any "something that I can depend on" when it comes to things like this. You need to understand the underlying concepts and then learn how to apply them to specific problems via lots of practice.

For most recursive problems, you need to identify two things -- the base case (or cases) and the recursive case.

Take your Fibonacci numbers as an example. What is the definition of the nth Fibonacci number? Simple, it's the sum of the prior two Fibonacci numbers.

So there's your recursive case.

Fib(n) = Fib(n-1) + Fib(n-2)

What's the base case? Here the first one that we can calculate directly is Fib(2), since for that we need Fib(1) and Fib(0). We can't compute Fib(1) recursively since we would need Fib(-1) which is undefined. So we have TWO base cases:

Fib(0) = 0
Fib(1) = 1

Notice that this can be simplified to

if (n < 2) then Fib(n) = n

So the pseudocode for your recursive implementation becomes very simply

Fib(n)
if (n < 2)
   return n
return Fib(n-1) + Fib(n-2)

I generally find that nailing down the recursive case is pretty easy and that then helps me see more clearly what the base case needs to be.

Very good explanation!
About the arguments of recursive..I always find it hard to decide which arguments to pass as input to my recrusive call ; what should i do?


Thank you very much

 

Very good explanation!
About the arguments of recursive..I always find it hard to decide which arguments to pass as input to my recrusive call ; what should i do?


Thank you very much

Write LOTS of recursive functions -- practice, practice, practice. This is a skill that needs to be honed through exercise.

 

About the arguments of recursive..I always find it hard to decide which arguments to pass as input to my recrusive call ; what should i do?

Read a bunch of recursive functions to get a sense of how they should look. Then practice, practice, practice.

 

Another thing that might help (or might make matters worse) is to try to learn a functional programming language like Lisp, which does not have loops at all and so all iteration has to be done via recursion. There are a lot of free online tutorials on Lisp/Scheme/Racket (which are all essentially the same thing). Just learning how to execute "normal" loops recursively might help you see the light.

 

Another thing that might help (or might make matters worse) is to try to learn a functional programming language like Lisp, which does not have loops at all and so all iteration has to be done via recursion. There are a lot of free online tutorials on Lisp/Scheme/Racket (which are all essentially the same thing). Just learning how to execute "normal" loops recursively might help you see the light.

thank you very much and I dont know how to thank you more !
could I ask for any suitable analogous of our roleplay life that represent the recursion manner/method?
once again I understand what the recursion is, but you know to be more confidence, you should visualize it on something related to our life to be stuck in your/my head ..


thanks !

 

Here what the lecturer has drawn for describing the recursive pattern .. But whenever I look at this I don't know how it's relevant to the recursion at all ....any one can explain how this realization represent recursive? and what's the arrows about?! he told us if we want to go to the right sub tree then we must pass the correct parameters in calling like F(tree->left) to go to the left sub tree but why if we want to go left then I must pass the parameter tree->left ?! how is it visualized like that? ; lets say I want to find the height of the tree .. who said that between every node the height is constant?! maybe between Node number 1 and number two the height is bigger then the node between two and node number three .. I guess I miss understanding the notion.


Thanks

 

could I ask for any suitable analogous of our roleplay life that represent the recursion manner/method?
once again I understand what the recursion is, but you know to be more confidence, you should visualize it on something related to our life to be stuck in your/my head ..

Imagine that your "function" for the day is to clean your house. The way we usually go about this is loosely recursive: to clean the house, we recursively run the function on smaller pieces of the house (bedroom, kitchen, etc.). In these smaller areas, we recursively run the function on even smaller pieces (bed, floor, counters, etc.), until the entire house is clean.

 

Imagine that your "function" for the day is to clean your house. The way we usually go about this is loosely recursive: to clean the house, we recursively run the function on smaller pieces of the house (bedroom, kitchen, etc.). In these smaller areas, we recursively run the function on even smaller pieces (bed, floor, counters, etc.), until the entire house is clean.

I understand the story ! but what does "we recursively run the function"? what does this term stand for?

 

I understand the story ! but what does "we recursively run the function"? what does this term stand for?

It's just a metaphor, as if internally we have a "clean()" function that our brain "runs" whenever it wants to clean the house. The important idea is that recursion uses a divide-and-conquer strategy: to solve a big problem, break it up into smaller pieces and solve the easier, smaller problems.

 

That’s not much different than running a series of subroutines, which would work for cleaning your house. It’s more like cleaning an unknown house, where the need for tasks is discovered as you go along and cannot be specified at the beginning.

 

That’s not much different than running a series of subroutines, which would work for cleaning your house.

That's precisely what a recursive function does: runs a sequence of functions. Each called function is independent and gets its own stack frame. The only unusual part is that all the functions have the same definition.

 

thank you very much and I dont know how to thank you more !
could I ask for any suitable analogous of our roleplay life that represent the recursion manner/method?
once again I understand what the recursion is, but you know to be more confidence, you should visualize it on something related to our life to be stuck in your/my head ..


thanks !

Imagine you need to sort a big pile of papers -- maybe by date. There are a number of ways to do this. One is to split the pile in two roughly equal pieces and sort each smaller pile. Now, with two sorted piles, it is very easy to combine them into a single sorted pile. But what if the two smaller piles are still more than you want to sort at one time? Well, split them into two smaller piles and sort those then combine then. You can repeat this as far as you want to go, stopping as soon as you get to a small enough pile that you are comfortable with just sorting it directly. If you really, really wanted to, you could continue this process down until you split piles into single pieces of paper and, at that point, that pile is sorted.

This is known as merge sort and it is one of the faster sorting algorithms out there -- and it is doubly-recursive.

I've come to use a variant of this whenever I have to sort a stack of papers. I actually use what is known as insertion sort to make a pile of sorted papers until it gets unwieldy. Then I just start making another pile. I do this until I've gone through all the papers and I know have several sorted piles. If I have five or fewer, I just merge them all at once by taking the next paper off of whatever stack it happens to be in. If I have more than five piles, I find I'm not very efficient at this and so I take sets of two or three piles and merge them until I get down to five.