# C - Recursion
Recursion is the process of repeating items in a self-similar way. In programming languages, if a program allows you to call a function inside the same function, then it is called a recursive call of the function.

---

### **Memoization Recursion**

Recursion is the technique of making a function call itself. This technique provides a way to break complicated problems down into simple problems which are easier to solve.

There is an example:

int climbStairs(int n){
    int a;
    if(n==0)
    {
        return 0;
    }
    else if(n==1)
    {
        return 1;
    }
    else if(n==2)
    {
        return 2;
    }
    else if(n>=3) 
    {
        a = climbStairs(n-1)+climbStairs(n-2);
    }
return a;
}

**Example Explained**
When the climbStairs() function is called, it adds parameter n to the sum of all numbers smaller than n and returns the result. When n becomes 0, the function just returns 0.

Using direct Recursion in 70.Climbing Stairs

---

### **Memoization Recursion**

This can be implemented by using an array to hold successive numbers in the sequence. For each recursive call, we check to see if the value has already been computed by looking in the cache. If has been previously computed, we return this value. Otherwise, we perform the computation and add this to the cache.

70.Climbing Stairs
![reference link]

int climbStairs(int n) {
    int arr[n+1];
	arr[0]=1;
	arr[1]=1;
	for(int i=2;i<=n;i++){
		arr[i]=arr[i-1]+arr[i-2];
	}
	return arr[n];
}

**Example Explained**
we can either take 1 step or 2 step at once.So In order to reach suppose 3rd stair we can either jump 2 steps from 1st stair or 1 step from 2nd stair. Total ways to reach 3rd stair will be sum of total ways to reach 1st stair + 2nd stair.

---

### **Previous Sum**
This one was Analysis based question if we observe the pattern of the answers then we will find that the final answer is the sum of previous two answers.

70.Climbing Stairs

int climbStairs(int n) {
  if(n==1)
  {
    return 1;
  }
  if(n==2)
  {
    return 2;
  }
  int n1=1,sum=0;
  int n2=2;
  for(int i=3;i<=n;i++)
  {
    sum=n1+n2;
    n1=n2;
    n2=sum;
  }
  return sum;
}