A Basic Recursive CTE and a Money Lesson

Another post for me that is simple and hopefully serves as an example for people trying to get blogging as #SQLNewBloggers.

When I was a six or seven year old, my Mom asked me a question. She asked if I’d rather have $1,000,000 at the end of the month, or a penny on day 1, with the note that each day of the month, she’d double what I’d gotten the first day. Doing quick math in my head, $0.01, $0.02, $0.04, etc, I said a million.

Was I right? Let’s build a recursive CTE.

Recursion is an interesting computer science technique that stumps lots of people. When I was learning programming, it seemed that recursion (in Pascal) and pointers (in C), were the weed out topics.

However, they aren’t that bad, and with CTEs, we can write recursion in T-SQL. I won’t cover where this might be used in this post, though I will give you a simple CTE to view.

There are two parts you need: the anchor and the recursive member. These are connected with a UNION ALL. There can be multiple items, but we’ll keep things simple.

I want to first build an anchor, which is the base for my query. In my case, I want to start with the day of the month, which I’ll represent with a [d]. I also need the amount to be paid that day, which is represented with [v]. I’ll include the $1,000,000 as a scalar at the end. My anchor looks like this:

WITH myWealth ( d, v)
AS (

— anchor, day 1
SELECT
‘d’ = 1
, ‘v’ = CAST( 0.01 AS numeric(38,2))
UNION ALL

Now I need to add in the recursive part. In this part, I’ll query the CTE itself, calling myWealth as part of the code. For my query, I want to increment the day by 1 with each call, so I’ll add one to that value.

SELECT
myWealth.d + 1

For the payment that day, it’s a simple doubling of the previous day. So I can do this a few days: addition or multiplication. I’ll use multiplication since it’s easier to read.

SELECT
myWealth.d + 1
, myWealth.v * 2

My FROM clause is the CTE itself. However I need a way to stop the recursion. In my case, I want to stop after 31 days. So I’ll add that.

UPDATE: The original code (<= 31) went to 32 days. This has been corrected to stop at 31 days.

FROM
myWealth
WHERE
myWealth.d <= 30

Now let’s see it all together, with a little fun at the end for the outer query.

WITH  myWealth ( d, v )
AS (
— anchor, day 1)
SELECT
‘d’ = 1
, ‘v’ = CAST(0.01 AS NUMERIC(38, 2))
UNION ALL
— recursive part, get double the next value, end at one month
SELECT
myWealth.d + 1
, myWealth.v * 2
FROM
myWealth
WHERE
myWealth.d <= 31
)
SELECT
‘day’ = myWealth.d
, ‘payment’ = myWealth.v
, ‘lump sum’ = 1000000
, ‘decision’ = CASE WHEN myWealth.v < 1000000 THEN ‘Good Decision’
ELSE ‘Bad decision’
END
FROM
myWealth;

When I run this, I get some results:

2016-05-17 18_48_04-Start

Did I make a good choice? Let’s look for the last few days of the month.

2016-05-17 18_48_16-Start

That $1,000,000 isn’t looking too good. If I added a running total, it would be worse.

SQLNewBlogger

If you want to try this yourself, add the running total and explain how it works.

About way0utwest

Editor, SQLServerCentral
This entry was posted in Blog and tagged , , . Bookmark the permalink.

8 Responses to A Basic Recursive CTE and a Money Lesson

  1. rsterbal says:

    Its a nice story, but a lot of effort for something that gets done in spreadsheet in a minute or two:

    Day Amount Running Amount
    1 0.01 0.01
    2 0.02 0.03
    3 0.04 0.07
    4 0.08 0.15
    5 0.16 0.31
    6 0.32 0.63
    7 0.64 1.27
    8 1.28 2.55
    9 2.56 5.11
    10 5.12 10.23
    11 10.24 20.47
    12 20.48 40.95
    13 40.96 81.91
    14 81.92 163.83
    15 163.84 327.67
    16 327.68 655.35
    17 655.36 1,310.71
    18 1,310.72 2,621.43
    19 2,621.44 5,242.87
    20 5,242.88 10,485.75
    21 10,485.76 20,971.51
    22 20,971.52 41,943.03
    23 41,943.04 83,886.07
    24 83,886.08 167,772.15
    25 167,772.16 335,544.31
    26 335,544.32 671,088.63
    27 671,088.64 1,342,177.27
    28 1,342,177.28 2,684,354.55
    29 2,684,354.56 5,368,709.11
    30 5,368,709.12 10,737,418.23
    31 10,737,418.24 21,474,836.47

    • way0utwest says:

      It’s not about the effort, it’s about the practice playing with an algorithm. There are much, much easier ( and more efficient) ways of calculating this. This was a chance to play with recursion.

  2. rsterbal says:

    A prettier version of the above table can be found at:

    https://sqlserver.miraheze.org/wiki/Penny_doubled_every_day

  3. rsterbal says:

    Right now the recursion that I find really interesting was posted by Phil Factor here: https://www.simple-talk.com/sql/sql-tools/automatically-creating-uml-database-diagrams-for-sql-server/

  4. Solomon says:

    Steve, I think your initial response to your mom was correct given that it is a trick question ;-). Since the other option was “a penny on day 1, with the note that each day of the month, she’d double what I’d gotten the first day”, then you would only be getting $0.02 each of the rest of the days of the month because that is double what you got on day 1. So with 30 days left, that is $0.60 on top of day 1 for a total of $0.61. 🙂

    Also, in your CTE, you need to set the upper limit to “myWealth.d <= 30" since using 31 got you a result showing 32 days.

    • way0utwest says:

      I may have misphrased. The question was the amount doubled every day, not that a penny is doubled once.

      Yeah, 32 days. I should have corrected that. My code didn’t quite match the explanation. I was more focused on playing with recursion than meeting the specs.

  5. Solomon says:

    Neither of those two things that I mentioned were meant as serious critiques. I was just having fun with a more literal interpretation of the stated problem, though I knew what you had intended. But it does show how important it is to verify the specifics of the feature request prior to implementation ;-).

    And no, the 32 vs 31 days is not super important, but I thought it should be clarified since this is example code for the benefit of teaching the concept. So, it might help to explain why the need to set the max to 30 in order to get 31 since it initially appears to meet expectations to have been set to <= 31 for the desire to get 31 days worth. That's all. And I do see that you have updated it (thanks), but the "all together" script still needs that update (and ideally the image, but I do get that time is limited and that part takes more time 😦 ) Again, I am just mentioning for completeness; overall, I think this is a good explanation of the concept :-).

Comments are closed.