_Nishachor's blog

How to think recursively?
By _Nishachor, history, 4 years ago, In English

As a beginner, I face lots of difficulties thinking a program recursively. After thinking for a while, I can tell the output of a recursive function but when I try to write a program recursively on my own, my head gets messy and I can't think properly after some time. I want to know how to think a program recursively in an intuitive way so that I can write a recursive program without thinking recursive tree or call stack every time. How do you think when you write a complex recursive solution?

  • Vote: I like it
  • +9
  • Vote: I do not like it

Comments Comments (8)
| Write comment?
»
4 years ago, # |
  Vote: I like it +35 Vote: I do not like it

to catch a rat you've gotta know how a rat thinks yunno, you've got to lay down the peanut butter. To think recursively your life has to reflect recursion, you study her and respect her before trying to catch her. #baddestguywisdomquotes #RecurrrSoundsLikeOkurrr

→ Reply
»
4 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Divide the problem into sub problems and deal with every sub problem as its function is 100% correct.Just think about how to calculate the current stage. knapsack for example can be divided as either to take (add its cost and weight) or leave the current item and deal with a new sub problem. And about the base case it's either going in a cycle or calling a function that will not help in the problem (idx==n or current weight is already greater than the limit in knapsack for example).

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

think about it like in math class f(x) = 4. but in this case, if f(x) = y, then you do f(y), for example. same thing with recursion. most of the time the easy recursion cases can be done like this, the hard recursion cases u shouldn't worry too much about until later on (i think the 641 div2B was a recursion problem)

→ Reply
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I suggest you practice some DFS(not BFS) problems on CF.

→ Reply
»
4 years ago, # |
  Vote: I like it +108 Vote: I do not like it

Thinking recursively is simple! Look at this blog for some examples.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    and that is why i am grey and you are orange.

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    And always remember to add the base case. For those who are stuck in this moment: Ctrl + W.

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Ever watched the movie Inception?

→ Reply