Converting iteration to a recursion

Question

Was watching this video By Anton Spraul : https://www.youtube.com/watch?v=oKndim5-G94&index=4&list=PLKQ5LYb497AZIZe9dBWy8GwLluVaMQVj0 wherein he talks about solving recursion by using an iterative function and a dispatcher function. I tried to find the nth fibonnaci number by using the same approach but the issue is that he uses the end values of an array in the dispatcher which are empty in my case. This is what i am trying to do:

//n is the nth fibonnaci number to be found.
int fibonacci(int fiboarray[], int number)
{
    int i = 2;
    for (i = 2; i < number; i++)
    {
        fiboarray[i] = fiboarray[i - 1] + fiboarray[i - 2];
    }

    return fiboarray[i - 1];
}
int fibonaccidispatcher(int fiboarray[], int number)
{
    if(number==0)return 0;
    int last=fiboarray[number-1]+fiboarray[number-2];
    fiboarray[number]=fibonaccidispatcher(fiboarray,number-1)+last;
    return fiboarray[number];


    // return diff;
}

I know the iterative function works directly but what i am trying to do is to use the approach in the video to convert it into an recursive function.

Alas that is not so easy in the case of Fibonacci sequence, because it has recursive degree 2. — Jean-Baptiste Yunès
– Jean-Baptiste Yunès, Commented Mar 2, 2018 at 9:23

Jean-Baptiste Yunès · Accepted Answer · 2018-03-02 09:43:52Z

A general scheme to replace iteration by recursion is:

for (int i=0; i<N; i++) {
    // some computation with i
}

can be replaced by:

void f(int i,int N) {
  if (i==N) return;
  // some computation with i
  f(i+1);
}
...
f(0,N);

Say you are computing factorial:

fact = 1;
for (int i=1; i<=N; i++) {
    fact = fact*i;
}

this can be replaced by:

int fact = 1;
void fact(int i,int ?) {
    if (i>N) return;
    fact = fact*i;
    fact(i+1);
}
...
fact(1,N);

For Fibonacci sequence:

int fib = 0;
int fib1 = 1;
int fib2 = 1;

for (int i=2; i<=N; i++) { // general case, needs to test for case 1 and 2...no really important
    fib = fib1+fib2;
    fib2 = fib1;
    fib1 = fib;      
}

recursive version is:

int fib = 0;
int fib1 = 1;
int fib2 = 1;

void fib(int i,int N) {
    if (i>N) return;
    fib = fb1+fib2;
    fib2 = fib1;
    fib1 = fib;
    fib(i+1,N);
}
...
fib(2,N);

Now if you want to avoid global variables, you can just write:

int fib(int basecase1, int basecase2, int i, int N) {
    if (i==1) return basecase1;
    if (i==2) return basecase2;
    if (i>=N) return basecase1;
    return fib(basecase1+basecase2, basecase1, i+1, N);
}
...
int result = fib(1,1,1,N);

For a call fib(1,1,1,5) you will have:

user5151179 · Accepted Answer · 2018-03-02 05:14:10Z

0

This doesn't answer your question at all, but you might be interested in how to solve this using multiple recursion:

private int fib(int no)
{
    if (no <= 1)
        return no;

    return fib(no - 1) + fib(no - 2);
}

answered Mar 2, 2018 at 5:14

user5151179

5852 silver badges10 bronze badges

1 Comment

Bissi singh Over a year ago

Well I know this will work ,but what I am trying to do is figure out a way to break down recursive approaches for more complex situations.

Collectives™ on Stack Overflow

Converting iteration to a recursion

2 Answers 2

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related