Why does recursion not work?


  • 0
    S

    Recursion does exactly what the following codes do. Why does it result in time limit exceed?

    int climbStairs(int n) {
    if(n<=0) return 0;
    if(n==1) return 1;
    if(n==2) return 2;
    int num_prev2=1;
    int num_prev=2;
    int result;
    for(int i=3;i<=n;++i){
    result=num_prev2+num_prev;
    num_prev2=num_prev;
    num_prev=result;
    }
    return result;

    }

  • 1
    S

    Recursion version:
    int climbStairs(int n) {
    if(n<=0) return 0;
    if(n==1) return 1;
    if(n==2) return 2;
    return climbStairs(n-1)+climbStairs(n-2);
    } //this code will result in time limit exceed

    }


  • 0
    L

    @songgaoxian Because the running time of this recursive code is incredibly large! Each call will generates two recursive calls, so it costs O(2^n) running time. Just think of how large 2^1000 is, if n = 1000.


  • 0
    N
    This post is deleted!

  • 0
    N

    @leodd Can you please explain why it should cost O(2^n)? cuz I thought cost of this recursion algorithm should be sum of Fibonacci sequence. So If n = 1000, total times of call should be Fib(1) + Fib(2) + Fib(3) + ... + Fib(999) + Fib(1000), instead of 2^1000.

    p.s. I agree the cost is still too high.


  • 0
    N

    @songgaoxian said in Why does recursion not work?:

    Recursion version:
    int climbStairs(int n) {
    if(n<=0) return 0;
    if(n==1) return 1;
    if(n==2) return 2;
    return climbStairs(n-1)+climbStairs(n-2);
    } //this code will result in time limit exceed

    }

    Intuitive recursion approach like "return climbStairs(n -1) + climbStairs(n - 2);" would surely cost too much and lead to TLE. Thus more work are needed when dividing the scale of problem. I cut n into half and then add three situations together. Here's AC code.

    class Solution {
    public:
        int climbStairs(int n) {
            if(n == 0)  return 1;
            if(n == 1 || n == 2)    return n;
            
            int a = climbStairs(n / 2); 
            int b = climbStairs((n - 1) / 2 - 1); 
            int c = climbStairs(n / 2 - 1);
            int d = climbStairs((n -1) / 2);
            
            return b * a + d * a + d * c;
        }
    };
    

  • 1

    @Necctor said in Why does recursion not work?:

    Can you please explain why it should cost O(2^n)?

    This problem is exactly like Fibonacci sequence, and although it's known that the naive recursion algorithm to generate Fib(n) is O(2^n), there's a tighter bound which is roughly O(1.6^2). It's easier to explain it as 2^n as follows:

    You have n stairs to climb, each stair is unique and no repetition (you won't climb the same stair twice, but in fact the numbers do repeat as and we have overlapping subproblems, that's why we use DP for it), so from counting it would be 2^n

    Another way to think about it, you have n stairs, at each stair you have 2 choices, either to jump 1 stair or 2 stairs, so at the first stair you n ways to jump either 1 stair or 2, then you have either n - 1 ways to jump 1 or 2 stairs or n - 2 ways to jump 1 or 2 stairs.

    Back to why it's not O(2^n) exactly is the following

    let's for example calculate for n = 4

                4
              /     \
            3         2
          /   \         \
        2      1         0
        |      |     
        0      0
    

    it would be exactly 2^n if each node has 2 children, but that's not the case cause some trees terminate with one child only

    I hope that's all make sense to you


  • 0
    H

    @Necctor hi,

    See
    climbStairs(n) = climbStairs(n-1) + climbStairs(n-2);
    climbStairs(n-1) = climbStairs(n-2) + climbStairs(n-3);
    climbStairs(n-2) = climbStairs(n-3) + climbStairs(n-4);

    you can see there're many duplicated calculation.
    that's why Dynamic Programming should be used: we can do it in bottom-up way.

    from climbStairs(1), climbStairs(2), climbStairs(3) until climbStairs(n)
    each subproblem is calculated once.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.