I need help with recursive functions

Question

I need help with recursive functions

Navigation

#1 by (0 votes)

1

I have a task that I do not understand how to start, they ask me to tell how many ways I can climb a staircase of N steps eg: pepito can climb 1 or 2 steps in how many ways can climb a staircase of 4 steps, to which I would have to show on screen

a) 1,1,1,1 (1 step and then 1 until you get to 4)

b) 1,1,2

c) 1,2,1

d) 2.2

I need your help please

python python-3.x

asked by Matias Alejandro Espinoza Tapi 26.10.2018 в 00:34

source

1 answer

Different onclick event for each part of a recyclerview Two click to change the item (slider)

score 0 · Answer 1

Have you tried anything? Instead of giving you the code with the solution, I'm going to give you some ideas so that you can try to get there by yourself.

The key to recursion is to implement a function that solves the trivial case (ex: ladder of 1 step or 2), and to solve more complex cases first solve a smaller ladder (calling itself) and use that solution to solve the biggest ladder.

In the case of the ladder you have to think ... "If I had a function that I pass the number of rungs of a ladder (say M) and returns the list with all possible forms to climb that ladder ... how could I use it to solve a ladder with more rungs, say N? "

If you stop to think a bit the solution could go like this:

I can start the ladder of N steps by climbing 1 step, or also by climbing 2. They are the only ways. Let's say I choose to raise p rungs to start.
Once the first steps are up, what remains in front of me is a smaller ladder, with N-p rungs.
Let's use the function that solves the minor ladder. I will return a list of ways to climb that sub-staircase. To each element of that list I add ahead the value of p
If I do the above twice, once for p=1 and once for p=2 , I already have all the ways to climb the ladder of size N.

Now, the miracle of recursion is that the other function that solves minor stairs is the same as the one that solves major stairs! It is enough to add code ahead to detect if the staircase to climb has only 1 or 2 steps so that in those cases return the trivial solutions "precalculated".

The pseudo-code would therefore be:

def escalera(N):
   si N==1 retornar una lista con un solo elemento [[1]], pues sólo hay una forma
           de subir una escalera de un escalón
   si N==2 retornar una lista con dos elementos [[1,1], [2]], pues hay dos formas
           de subir una escalera de dos escalones. O de uno en uno, o los dos a la vez
   Para el resto de casos:
   repetir para p=1 y p=2
      obtener soluciones para escalera de tamaño N-p
      a cada solución concatenarle p por delante
   retornar la lista de soluciones halladas.