I come from a physics background, and thus, lots of maths. I find easy to spot problems well suited to recursive/dynamic programming solutions by finding similarities with proof by induction.

In proof by induction you have two parts:

• you prove that if something is true for iteration N, it is also true for iteration N+1
• you prove that it is true for iteration 1

In recursive programming/dynamic programming:

• you identify an exit condition (for example, you hard wire the solution for iteration 1)
• you calculate solution for iteration N+1 given the solution for iteration N

So, as others answered, it is a matter of experience and picking the hints, but you can re-use other skills to guide you. After that, you need to always have the two parts which I mentioned: if you don't, then it won't work.

For example, to generate all the permutations of a set:

• exit condition: if you only have one element, return it
• recursion: the permutations of a set of N+1 items are the N+1 sets of permutations you get by choosing each element and appending all the permutations of the subset.

I come from a physics background, and thus, lots of maths. I find easy to spot problems well suited to recursive/dynamic programming solutions by finding similarities with proof by induction.

In proof by induction you have two parts:

• you prove that if something is true for iteration N, it is also true for iteration N+1
• you prove that it is true for iteration 1

In recursive programming/dynamic programming:

• you identify an exit condition (for example, you hard wire the solution for iteration 1)
• you calculate solution for iteration N given the solution for iteration N-1

So, as others answered, it is a matter of experience and picking the hints, but you can re-use other skills to guide you. After that, you need to always have the two parts which I mentioned: if you don't, then it won't work.

For example, to generate all the permutations of a set:

• exit condition: if you only have one element, return it
• recursion: the permutations of a set of N items are the N sets of permutations you get by choosing each element and combining the with all the N-1 sets of (many) permutations of the subset you get by removing the element.

I come from a physics background, and thus, lots of maths. I find easy to spot problems well suited to recursive/dynamic programming solutions by finding similarities with proof by induction.

In proof by induction you have two parts:

• you prove that if something is true for iteration N, it is also true for iteration N+1
• you prove that it is true for iteration 1

In recursive programming/dynamic programming:

• you identify an exit condition (for example, you hard wire the solution for iteration 1)
• you calculate solution for iteration N+1 given the solution for iteration N

So, as other answered, it is a matter of experience and picking the hints, but you can re-use other skills to guide you. After that, you need to always have the two parts which I mentioned: if you don't, then it won't work.

For example, to generate all the permutations of a set:

• exit condition: if you only have one element, return it
• recursion: the permutations of a set of N+1 items are the N+1 sets of permutations you get by choosing each element and appending all the permutations of the subset.

I come from a physics background, and thus, lots of maths. I find easy to spot problems well suited to recursive/dynamic programming solutions by finding similarities with proof by induction.

In proof by induction you have two parts:

• you prove that if something is true for iteration N, it is also true for iteration N+1
• you prove that it is true for iteration 1

In recursive programming/dynamic programming:

• you identify an exit condition (for example, you hard wire the solution for iteration 1)
• you calculate solution for iteration N+1 given the solution for iteration N

So, as others answered, it is a matter of experience and picking the hints, but you can re-use other skills to guide you. After that, you need to always have the two parts which I mentioned: if you don't, then it won't work.

For example, to generate all the permutations of a set:

• exit condition: if you only have one element, return it
• recursion: the permutations of a set of N+1 items are the N+1 sets of permutations you get by choosing each element and appending all the permutations of the subset.