# Writing a recursive function

## Introduction

Recursive functions are sometimes hard to write because we are not use to thinking about problems recursively. However, there are two things you should do:

1. state the base case (aka easy case). what argument values will lead to a solution so simple that you can simply return that value  (or do a very simple calculation and return that value?
2. state the recursive case. if you are given something other than the base case how can you use the function itself to get to the base case
3. Recursion is about stating a problem in terms of itself.  The solution to the current problem is consist of taking a small step and restating the problem.

## Example:  The factorial function.  

Write a function that is given a single argument n and returns n!.  n! = n\*(n-1)\*(n-2) ...2\* 1.  For example 4! = 4 \* 3 \* 2 \* 1 , by definition, 0! is 1

How would you do it recursively?  

Lets start with base case.  What value of n is it easy to come up with the result of n!?

0 is easy.. by definition 0! is 1.  1 is also easy because 1! = 1 

Thus, we can establish that any value 1 or less is a base case with result of 1.

Now, the recursive case... how can we state factorial in terms of itself?

Let's consider this example: 5! = 5\* 4\* 3\* 2 \* 1.  but... we can restate this as 5! = 5 \* (4\*3\*2\*1) but ... 4\*3\*2\*1 is just 4!.  So, 5! = 5 \* 4!.   In general we can say that n! = n \* (n-1)!.  We can pretty apply this idea to our function. 

```cpp
unsigned int factorial(unsigned int n){
    unsigned int rc = 1 ;              //base case result
    if(n > 1)                 //if n > 1 we  have the recursive case
        rc= n * factorial(n-1);  //rc is n * (n-1)!
    }
    return rc;
}
```

{% hint style="info" %}
Recursion works by magic... ok it really doesn't but it might be easier to think of it that way.  Essentially what recursion does is it starts with the idea that you already have a working function.  (ie factorial already works).  The base case actually ensures it does work at least for some values of n.  The recursive case is simply using a working function to solve the problem.  Don't think about it too much and it will be a lot easier to code. 
{% endhint %}


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://catherine-leung.gitbook.io/data-strutures-and-algorithms/recursion/how-to-write-a-recursive-function.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.