Where is the count stored?

#1

Hey everyone. So I think I understand how this code works. It takes the total number of steps, whatever you set n equal to, and subtracts 1, 2, or 3 as applicable and recurses that process. But I don’t understand where/how the results are stored. It looks like they’re in findStep(n), but I don’t see the final piece of the path that leads to that being the desired output.

The program was written in response to the following problem:

Child can take 1, 2, 3 steps. Total steps he has to take is n. Find no. Of ways he can traverse those steps.

So again, my question is: where is the count of the number of ways stored? I don’t see how it can be in findStep(n) because that keeps changing the whole time according to all the subtractions. But the main method sure makes it seem like it has to be in findStep(n).

// Program to find n-th stair
// using step size 1 or 2 or 3.
import java.util.*;
import java.lang.*;
 
public class GfG{
     
    // Returns count of ways to reach
    // n-th stair using 1 or 2 or 3 steps.
    public static int findStep(int n)
    {
        if (n == 1 || n == 0) 
            return 1;
        else if (n == 2) 
            return 2;
      
        else
            return findStep(n - 3) + 
                   findStep(n - 2) +
                   findStep(n - 1);    
    }
     
    // Driver function
    public static void main(String argc[]){
        int n = 4;
        System.out.println(findStep(n));
    }
}
 
/* This code is contributed by Sagar Shukla */
#2

Your variables are being stored on the stack
It’s a bit computer science-y to explain here.
Research the stack and the heap. Also research the stack data structure.

Some abstraction
Basically your variables are getting put into a box. You can add to the box, but can only remove the top item in the box.
As your function recursively calls itself, it throws the count variable into a stack. variables are popped off the stack to be returned to the calling function

#3

Technically there are no values in the stack, but uncompleted calls.

Below is symbolic pseudo code of a cursory trace of the function when n is 4:

  f(4) =>
  return                        # first return call pushed onto the stack
  f(n - 3)    =>   f(1)  =>  1  : addend 
  + f(n - 2)  =>   f(2)  =>  2  : addend
  + f(n - 3)  =>   f(3)  =>
    return                      # second return call pushed onto stack
    f(n - 3)    => f(0)  =>  1  : addend
    + f(n - 2)  => f(1)  =>  1  : addend
    + f(n - 1)  => f(2)  =>  2  : addend

No more calls, the stack winds down by returning the latest call (the resulting value) which is added to the earlier call and it’s one and done.

Output:

7

Run through the addends in the above. See how they add up? The values are not held as much as resultant as the stack unwinds.

The code ported to Python…

def find_step(n):
  if n == 1 or n == 0: return 1
  elif n == 2: return 2
  else: return \
    find_step(n - 3) + \
    find_step(n - 2) + \
    find_step(n - 1) 
     
print(find_step(4))

Every recursive function can be explained in one way or another. This one was simple because n is small. When it is 9, the result is 149, but the stack illustration would be cumbersome with some seven returns in the call stack.

We can also look at the mathematical principle behind why a recusion works (or doesn’t).

>>> find_step(1)
1
>>> find_step(2)  1 + 1
2
>>> find_step(3)  2 + 1 + 1
4
>>> find_step(4)  4 + 2 + 1
7
>>> find_step(5)  7 + 4 + 2
13
>>> find_step(6)  13 + 7 + 4
24
>>> find_step(7)  24 + 13 + 7
44
>>> find_step(8)  44 + 24 + 13
81
>>> find_step(9)  81 + 44 + 24
149
>>>

See a pattern there? That tells us this sequence has a general term with t1, t2, and t3 defined as the base of the sequence.

This suggests another Fibonacci sort of sequence which would make a great follow up assignment to this one. Write a program that uses an iterative algorithm to compose this sequence, and sum it. Chances are that for larger numbers your program will blow the doors off the above recursion in terms of clock ticks.

>>> u = [1,2,4]
>>> for x in range(3, 9):
	u.append(sum(u[x-3:x]))

	
>>> u
[1, 2, 4, 7, 13, 24, 44, 81, 149]

This all boils down to…

>>> def seq(n):                        # public function has return
	u = [1,2,4]
	for x in range(3, n):          # for (x = 3, x < n; x++)
	    u.append(sum(u[x-3:x]))    # push slice sum
	return u

>>> seq(9)
[1, 2, 4, 7, 13, 24, 44, 81, 149]
>>> def term(n):
	return seq(n)[-1]              # slice

>>> term(9)
149
>>>

You will have to port it over to Java, since that is not my native language, but the logic is all there.

As in JavaScript, I doubt that Java supports negative indexes. But they both have a slice method that does.

#4

Thanks for attributing the code. I gave your topic a vote because of the attribution, and because it is a good question to bring up.

#5

This topic was automatically closed 7 days after the last reply. New replies are no longer allowed.