# Recursion

A recursive function is defined in terms of *base cases* and *recursive steps*.

* In a base case, we compute the result immediately given the inputs to the function call.
    
* In a recursive step, we compute the result with the help of one or more *recursive calls* to this same function, but with the inputs somehow reduced in size or complexity, closer to a base case.
    

Consider writing a function to compute factorial. We can define factorial in two different ways:

| Product |
| --- |

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1712161650324/af9ec87b-f987-4ad9-a837-5fd5446bfe64.png align="center")

| Recurrence relation |
| --- |

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1712161686841/f4a8ce2f-72ca-4d00-8e24-94151d650b0f.png align="center")

which leads to two different implementations:

### Iterative

```c
public static long factorial(int n) {
  long fact = 1;
  for (int i = 1; i <= n; i++) {
    fact = fact * i;
  }
  return fact;
}
```

### Recursive

```c
public static long factorial(int n) {
  if (n == 0) {
    return 1;
  } else {
    return n * factorial(n-1);
  }
}
```

In the recursive implementation on the right, the base case is *n = 0*, where we compute and return the result immediately: *0!* is defined to be *1*. The recursive step is *n &gt; 0*, where we compute the result with the help of a recursive call to obtain *(n-1)!*, then complete the computation by multiplying by *n*.

To visualize the execution of a recursive function, it is helpful to diagram the *call stack* of currently-executing functions as the computation proceeds.

Let’s run the recursive implementation of `factorial` in a main method:

```java
public static void main(String[] args) {
    long x = factorial(3);
}
```

At each step, with time moving left to right:

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1712160606259/1101bcf6-42fe-4f63-8a7e-609ef99b7153.png align="center")

In the diagram, we can see how the stack grows as `main` calls `factorial` and `factorial` then calls *itself*, until `factorial(0)` does not make a recursive call. Then the call stack unwinds, each call to `factorial` returning its answer to the caller, until `factorial(3)` returns to `main`.

Another common example is the Fibonacci series:

```c

int fibonacci(int n) {
    if (n == 0 || n == 1) {
        return 1; // base cases
    } else {
        return fibonacci(n-1) + fibonacci(n-2); // recursive step
    }
}
```

Fibonacci is interesting because it has multiple base cases: n=0 and n=1.

Notice that where factorial’s stack steadily grows to a maximum depth and then shrinks back to the answer, Fibonacci’s stack grows and shrinks repeatedly over the course of the computation. Here is another representation of recursive function calls, called a recursion tree:

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1712162006481/ac0419f1-1de7-4b85-b011-11f4c2de7f91.jpeg align="center")