How can I simulate recursive func (which has more than recursive call inside) iteratively

Question

I am trying to get deep into understanding the recursion and have the full picture in my mind actually, I know how to make recursive iteratively using stack with normal functions like factorial function:

int Fact(long n)
{
    if(0>n)
        return -1;
    if(0 == n)
        return 1;
    else
        return ( n* Fact(n-1));
}

and sum function :

//assume n >0
int Sum(long n)
{
    if(0 == n)
        return 0;
    else
        return ( n+ Sum(n-1));
}

But what if a function has more than one recursive call and uses return value of the whole function for the two calls?

like :

Func(int n)
{
   int sum;
   int fact;
   if (n<=1)
   {
       return 1;
   }
   else 
   {
       sum =n+Func(n-1);
       fact=n*Func(n-1);
       return sum+fact;
   }
}

Pretty much the same thing. The first call to `Func` will recurse to completion and then the second call to `Func` will recurse to completion. The results are added and returned. Note in a case like this where you are likely to get a lot of repeated work you should look into [memoization](https://en.wikipedia.org/wiki/Memoization). In this case even a simple `int temp = Func(n-1); sum = n+temp; fact = n*temp;` would save a lot of work. — user4581301, May 04 '22 at 00:40
This is a bad example, because you only have to call Func once recursively. The second call to `Func(n-1)` will yield the exact same result. So unrolling it is as trivial as your two previous examples. — bitmask, May 04 '22 at 01:14
Your `Func` also has misleading variable names, because it doesn't calculate *either* the sum nor the factorial, because you return `sum + fact`. If you wanted to do that, you should have one call returning a structure with two members, e.g. `std::pair Func(int n) { if (n >1) { auto [sum, fact] = Func(n-1); return { n + sum, n * fact}; } else { return { 1, 1 }; } }` — Caleth, May 05 '22 at 09:32

wohlstad · Answer 1 · 2022-05-05T07:34:29.480

As already noted in the comments (see @bitmask's comment above), your Func is not a good example for multiple recursion.

Since this is for learning purposes, I'd like to introduce a classic example for multiple recursion. It is the following implementation for fibonaci series (Fibonacci - Wikipedia). Each number in the series (except the initial 2) is the sum of it's 2 predecessors.

The code below prints the 10 first elements in the series using multiple recursion:

#include <iostream>

int fib(int n)
{
    if (n <2) {
        return n;
    }
    return fib(n - 1) + fib(n - 2);
}

void main()
{
    for (int i = 0; i < 10; ++i)
    {
        std::cout << fib(i) << ",";
    }
}

As explained in the comments, multiple recursion works very similar to single recursion. The calls will be done in an order similar to the way DFS (Depth-first search - Wikipedia) is working. I.e. the first recuresive call will complete (including all the recursive calls made by it), then the second will be executed.

Note: my answer is based on the understanding that the question is in the context of studying the subject. However - using recursion causes some performance penalties (the cost of a function calls, and using the stack for it). There are usually more efficient ways to implement solution to problems like that. In the case of fibonaci if you need to generate multiple elements in the series, it's more efficient to do it iteratively. You need only to keep track of previous element and the one before it.

You can see here more about the subject in general: recursion versus iteration.

How can I simulate recursive func (which has more than recursive call inside) iteratively

1 Answers1