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.

Photo by Natalya Letunova on Unsplash

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,

Fn =0,1,1,2,3,5,8,13,21,34...

Mathematically,

F0=0

F1=1

Fn=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:

%dw 2.0
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.

%dw 2.0
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 nth 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 500th digit in the Fibonacci series.

%dw 2.0
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 500th 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.

%dw 2.0
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 😊😊😊



-

Comments

Post a Comment

Popular posts from this blog

DateTime formatting using xp20:format-dateTime ()

xs:dateTime Format In XML, we generally use xs:dateTime(xs:xmlns="http://www.w3.org/2001/XMLSchema") data type to store date time data. The generic representation of date time, that is supported by xs:dateTime in xml: YYYY-MM-DDThh:mm:ss[.SSS][Z|(+|-)hh:mm] Example :  2019-09-11T10:16:31.943+05:30 Code Description Example YYYY represents a 4-digit year 2019 MM represents a 2-digit month 09 DD represents 2-digit date 11 hh represents 2-digit hours 10 mm represents minutes in 2-digits 16 ss represents seconds in 2-digits 31 SSS represents milliseconds 943 T represents time separator T Z represents UTC time zone or 0 time zone offset (+|-)hh:mm represents time zone offset +5:30 Few more valid examples : 2019-09-11T21:32:52, 2019-09-11T21:32:52+02:...
Read more

Create Delimited String from XML Nodes and Vice Versa in SOA 12c

A delimited string is a string representation of data separated by a delimiter(e.g. ","). A simple representation of the delimited string will look like. Delimited String Examples Sample-1-- Delimiter as ","        Value1,Value2,Value3   Sample-2-- Delimiter as "|"        Value1|Value2|Value3 If we want to represent the above set of delimited values in the form of an XML document under some root and parent tag. The representation will look like this. XML Example <root xmlns="http://test.com/sample/xml">   <Values>     <value>Value1</value>     <value>Value2</value>     <value>Value3</value>   </Values> </root> Sometimes we may need to convert values coming in delimited string to an xml document or vice versa. Since delimited strin...
Read more

Import and Export MDS artifacts in SOA 12c

Image
Oracle SOA-MDS (Metadata Store) repository can be used to access artifacts that can be shared among various SOA composites. For example, we have one common schema for a business fault that is consumed by various applications. Instead of having a localized copy of that schema file in each SOA composite, we can have it in a centralized repository (SOA-MDS). Another benefit of using SOA-MDS is that we can change the file at runtime and need not redeploy the complete code. While developing SOA composites, we use SOA design-time repository, later these changes can be synced to the SOA servers. In this article, we will discuss 2 ways to sync the artifacts available in the SOA design-time repository and the SOA servers. Establishing the connection to SOA-MDS in Jdeveloper. Using SOA em console or Fusion Middleware control console. Moving a file between SOA composite to SOA design-time MDS repository Let's assume, we created a businessFault.xsd which wi...
Read more