### Experimenting Recursion in DataWeave - Fibonacci Series

In various programming languages, **recursion** is a process in
which a method or function calls itself to simplify a complicated problem.
Understanding recursive solution sometimes become difficult. Let's try to
solve a mathematical problem through recursion with a twist by using
**DataWeave**. The Fibonacci series is a generic use case that recursion can solve. This
is a very generic question in programming interviews.

## What is Fibonacci Series?

A Fibonacci series is a set of integers starting with 0 followed by 1, and a series continuing with the sum of the preceding two integers in the sequence. For example,

F_{n} =0,1,1,2,3,5,8,13,21,34...

### Mathematically,

F_{0}=0

F_{1}=1

F_{n}=F_{(n-1)} + F_{(n-2)}

Now transforming the above logic in the form of a recursive function to find the nth digit in the Fibonacci series.

### DataWeave Recursive Function:

output application/json

fun fib_r(n)=

if (n<=0) 0

else if (n==1) 1

else

fib_r(n-1) + fib_r(n-2)

---

{

recursive:fib_r(9)

}

**Output**

"recursive": 34

}

Testing on dataweave playground and increasing the value of

**n**. The moment we increase the value beyond

**27**, we get an

**ERROR**.

### ERROR?

The error shows the execution time taken by dataweave is more than 2.5 seconds. But how do we know how much time is taken by the recursive function? Is there a way to capture the execution time within DataWeave without any custom code/java modules? It's a yes, The DataWeave has a utility module Timer, which can be used to capture execution time as well as the result of the functions.

import * from dw::util::Timer

output application/json

fun fib_r(n)=

if (n<=0) 0

else if (n==1) 1

else

fib_r(n-1) + fib_r(n-2)

---

{

recursive:time(()->fib_r(27)),

recursive_d:duration(()->fib_r(27))

}

**Output**

"recursive": {

"start": "2023-06-13T16:33:29.053017Z",

"result": 610,

"end": "2023-06-13T16:33:29.059367Z"

},

"recursive_d": {

"time": 6,

"result": 610

}

}

Duration gives us the time taken by function execution in milliseconds and the time function output the start and end timestamp of the execution. With this, the execution time can be measured easily.

Now, the real issue is if we need to find the
**n _{th}** digit(greater than

**27**) in the Fibonacci series by optimizing space and time.

**How can that be done?**

Going back to programming days, there is a way of using

**Tail Recursion**. Now what exactly is tail recursion?

** Tail recursion** is using the recursive function as the last statement
of the function. The benefit of this approach is it optimises the space as
the function doesn't need to keep the track of last 2 execution results.
Since the result is populated as part of the last execution statement of the
function. Putting the coding hats again for the DataWeave.

With the new function let's find out the
**500 _{th} digit in the Fibonacci series**.

import * from dw::util::Timer

output application/json

fun fib_r(n)=

if (n<=0) 0

else if (n==1) 1

else

fib_r(n-1) + fib_r(n-2)

//tail recursion

fun fib_tr(n, x=0, y=1)=

if(n<=0)

x

else if (n==1)

y

else

fib_tr(n-1,y,x+y)

---

{

recursive:time(()->fib_r(5)),

tailRecursive:time(()->fib_tr(500))

}

**Output**

"recursive": {

"start": "2023-06-13T16:48:46.007784Z",

"result": 5,

"end": "2023-06-13T16:48:46.007897Z"

},

"tailRecursive": {

"start": "2023-06-13T16:48:46.007902Z",

"result": 139423224561697880139724382870407283950070256587697307264108962948325571622863290691557658876222521294125,

"end": "2023-06-13T16:48:46.010339Z"

}

}

In nearly 4 milliseconds, the new tail recursive function can give results
for the **500 _{th} digit **in the series.

## Can we improve the timings further?

In dataweave, we have a "reduce" function, which can be used to get output for the Fibonacci series even faster. Re-writing the logic with the "reduce" function is kind of challenging. After multiple trials and errors, one way is as below.

import * from dw::util::Timer

output application/json

fun fib_r(n)=

if (n<=0) 0

else if (n==1) 1

else

fib_r(n-1) + fib_r(n-2)

//tail recursion

fun fib_tr(n, x=0, y=1)=

if(n<=0)

x

else if (n==1)

y

else

fib_tr(n-1,y,x+y)

//with reduce

fun fib_rr(n)=

if(n<=0)

0

else

if(n==1)

1

else

([2 to n][0] reduce ((i,acc=[0, 1]) -> acc + (acc[i-1] + acc[i-2])))[n]

---

{

recursive:time(()->fib_r(5)),

tailRecursive:time(()->fib_tr(500)),

reduce:time(()->fib_rr(500))

}

**Output**

"recursive": {

"start": "2023-06-13T17:04:41.724469Z",

"result": 5,

"end": "2023-06-13T17:04:41.72455Z"

},

"tailRecursive": {

"start": "2023-06-13T17:04:41.724555Z",

"result": 139423224561697880139724382870407283950070256587697307264108962948325571622863290691557658876222521294125,

"end": "2023-06-13T17:04:41.726913Z"

},

"reduce": {

"start": "2023-06-13T17:04:41.726923Z",

"result": 139423224561697880139724382870407283950070256587697307264108962948325571622863290691557658876222521294125,

"end": "2023-06-13T17:04:41.729307Z"

}

}

The above DataWeave script is one of the many ways to solve the problem. On
comparing all three approaches, the solution using **reduce **function
performs **best of all**.

Please share your valuable feedback πππ

very useful post

ReplyDelete