How to analysis the complexity of this LIS program? I found a pseudocode online and I don't know why the complexity of it is $O(2^N)$, according to the site.
Given a fixed curr, the for-loop in lis_ending_here(...) will recursively call curr times itself will new curr range from 0 to curr-1, then I stuck here and don't know what's the next step to get the conclusion $O(2^N)$. You can also provide me resource (i.e. book name) which is about the technique to analysis the complexity of recursion, since I don't know what are the beginner friendly ones.
int lis_ending_here(int arr[], int curr)
{
    // Only one subsequence ends at first index, the number itself
    if(curr == 0)
        return 1
    int ans = 1
    for(i = curr-1 to 0, decrement of -1)
        if(arr[i] &lt; arr[curr])
            ans = max(ans, 1 + lis_ending_here(arr, i))
    return ans
}
int longest_increasing_subsequence(int arr[], int N)
{
    // Because a single number can be a subsequence too
    int max_ans = 1
    for(i = 0 to N-1)
        max_ans = max(max_ans, lis_ending_here(arr, i))
    return max_ans
}
The worst case running time of your first procedure satisfies the recurrence
$$
T(n) = T(n-1) + \cdots + T(1) + O(1).
$$
The worst case running time of your second procedure is $T(n) + \cdots + T(1) + O(1)$, which we can identify with $T(n+1)$. Thus it suffices to understand the first recurrence.
Let us assume replace $O(1)$ with $1$, obtaining the recurrence
$$
T(n) = T(n-1) + \cdots + T(1) + 1.
$$
Therefore
$$
T(n+1) = T(n) + [T(n-1) + \cdots + T(1) + 1] = 2T(n).
$$
Consequently, $T(n) = 2^{n-1} T(1) = 2^{n-1}$.
If we replace $1$ back with $O(1)$, we get $T(n) = O(2^n)$.