Recursion in Excel and Power Query - 1

In this post, I will demonstrate recursion in Excel and Power Query with some basic examples.

Example 1:

You are on a set of stairs that are numbered 100 - 0 from top to bottom. You are given your starting stair number, a stride width (meaning how many stairs you step down at a time) and being walking down. Return an array containing every stair you step on. Don't step below 0, it's Lava and you'll burn/fail.

LAMBDA-1:

=LET(l,LAMBDA(l,start,step,IF(start-step<0,start,VSTACK(start,l(l,start-step,step)))),l(l,68,3))

Result:

={68;65;62;59;56;53;50;47;44;41;38;35;32;29;26;23;20;17;14;11;8;5;2}

Let's begin with a starting position of 68 and a step of 3.

The base condition states that if the starting number minus the step is less than 0, the recursion should terminate and return the starting number. If not, the function will move down 3 steps to record the stair number.

68 minus 3 equals 65, which means our function records 68 and 65.

Next, 65 minus 3 equals 62, so now our function records 68, 65, and 62.

When we reach the 23rd stride, the starting position is 2. Since 2 minus 3 is less than 0, the recursion stops at stair 2.

LAMBDA-2:

=LET(l,LAMBDA(l,start,step,IF(start-step<0,HSTACK(start,1),LET(c,l(l,start-step,step),HSTACK(@c,INDEX(c,2)+1)))),l(l,68,3))

Result:

={2,23}

This will help us to get last stair and the number of strides to reach the last stair (which means number of recursion call)

Power Query:

let

fx = ( st as number, sp as number ) as list => if st - sp < 0 then {st} else {st} & @fx(st-sp,sp),

Result = Table.FromValue(fx(68,3), [DefaultColumnName = "Result"])

in

Result

Example 2:

Input:

Cell C2 contains the Total Amount, and the denominations are listed across the range B4:H4.

Denominations = {200,100,50,20,10,5,1}

Task:

Create a formula that calculates the count of each denomination such that the sumproduct of the counts and denominations equals the total amount.

LAMBDA:

=LET(l,LAMBDA(ME,n,Rng,LET(v,INT(n/@+Rng),IF(COUNT(Rng)=0,n,HSTACK(v,ME(ME,MOD(n,@+Rng),DROP(Rng,,1)))))),DROP(l(l,C2,B4:H4),,-1))

Arguments of custom function,

ME - Keyword for the name of the function itself.

n - Total Amount,

Rng - Denomination range (B4:H4),

In each iteration,

Rng - The leftmost column of Rng is dropped.

n - The remainder of the amount divided by the first value in Rng.

The iteration ends when COUNT(Rng) equals zero.

Power Query:

let

N = 1543,

D = {200,100,50,20,10,5,1},

fx = (n as number, l as list) as list => [a = Number.IntegerDivide(n,l{0}) , b = if l = {} then {} else {a} & @fx(Number.Mod(n,l{0}),List.Skip(l))][b],

Result = fx(N,D)

in

Result

Example 3:

Task:

Generate Hailstone Sequence also known as Collatz conjecture starting from given number by following these rules:

1. If n is even, divide it by 2.

2. If n is odd, multiply it by 3 and add 1.

3. Repeat the process with the resulting number.

Eventually, all hailstone sequences are believed to end in the cycle 4, 2, 1.

For example, starting with n=7

the sequence is 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1.

Excel:

=LET(l,LAMBDA(l,n,IF(n=1,n,VSTACK(n,l(l,IF(ISODD(n),n*3+1,n/2))))),l(l,1301))

Power Query:

let

 fx = (n as number) as list => [a = if Number.IsOdd(n) then n * 3 + 1 else n/2, b = if n = 1 then {n} else {n} & @fx(a)][b],

 Result = fx(1301)

in

 Result