Recursion

In Java, when we call recursion method it always store in the stack memory and it will work again and again until stack overflow error.

By proven this problem, we need to set base case in the recursive function to stop the process and return something when it’s get called.

What is Based case?

Based case is a condition inside your method can return without recursion called.

Example: Fibonacci number

The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,

F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), for n > 1.

Given n, calculate F(n).

Example 1:

Input: n = 2
Output: 1
Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1.

Solution

class Solution {
    public int fib(int n) {
       if(n == 0) return 0;
       if(n == 1) return 1;
       return fib(n-1)+fib(n-2); 
    }
}

https://leetcode.com/problems/fibonacci-number/