How can a recursive call in a for loop be optimized?

Question

I would like to know how a recursive function called in a loop of its own definition could be optimized like a tail call so as not to suffer from performance and stack size.

Typically, with pseudo code:

fun example(x):
    if (something):
        return // Stop the recursion
    else:
        for (/*...*/):
            example() // Recursive call

For a concrete example, I would like to know how to apply such an optimization on the following program, found here:

// C program to print all permutations with duplicates allowed 
#include <stdio.h> 
#include <string.h> 

/* Function to swap values at two pointers */
void swap(char *x, char *y) 
{ 
    char temp; 
    temp = *x; 
    *x = *y; 
    *y = temp; 
} 

/* Function to print permutations of string 
   This function takes three parameters: 
   1. String 
   2. Starting index of the string 
   3. Ending index of the string. */
void permute(char *a, int l, int r) 
{ 
   int i; 
   if (l == r) 
     printf("%s\n", a); 
   else
   { 
       for (i = l; i <= r; i++) 
       { 
          swap((a+l), (a+i)); 
          permute(a, l+1, r); // Recursive call to be optimized
          swap((a+l), (a+i));
       } 
   } 
} 

/* Driver program to test above functions */
int main() 
{ 
    char str[] = "ABC"; 
    int n = strlen(str); 
    permute(str, 0, n-1); 
    return 0; 
}

If the recursion becomes too deep, there is a risk of stack overflow. So how could we avoid that with this style of recursive functions (if possible, without drastically modifying the algorithm)?

The tail call optimization requires that the recursive call happens at the tail position. Yours does not. — Antti Haapala
– Antti Haapala, Commented May 16, 2020 at 14:59
Yes, I know. I'm just asking how to proceed in order to optimize the style of case I present. — Foxy
– Foxy, Commented May 16, 2020 at 15:03
You can not, a function is tail recursive when calling itself is the last pending thing to do, in your case there is another operation (swap) pending, furthermore it is called in a loop, so no, assume that all vars (sizeof(int) * 3) must be copied and accumulated in the stack for each call. — David Ranieri
– David Ranieri, Commented May 16, 2020 at 15:24
@Nelfeal why not true?, it depends on how long is the string, are we talking of few bytes, KBs, MBs? reading/writing to the stack is very very fast even using a lot of iterations, calling malloc is very very expensive — David Ranieri
– David Ranieri, Commented May 16, 2020 at 15:44
@DavidRanieri Why would an iterative algorithm need to copy the string if a recursive one does not? You can literally emulate the recursive algorithm with a custom stack in an iterative one. No need for any allocation, except maybe for the custom stack itself (but I believe you actually don't need one). — Nelfeal
– Nelfeal, Commented May 16, 2020 at 16:05

Nelfeal · Accepted Answer · 2020-05-16 16:01:00Z

3

This does not produce the exact same output, but is an iterative way of printing all permutations of a string. Adapted from cppreference.com.

void reverse(char *a, int l, int r)
{
    while ((l != r) && (l != --r)) {
        swap(a+(l++), a+r);
    }
}

bool next_permutation(char *a, int l, int r)
{
    if (l == r) return false;
    int i = r;
    if (l == --i) return false;

    while (true) {
        int i1 = i;
        if (a[--i] < a[i1]) {
            int i2 = r;
            while (!(a[i] < a[--i2]))
                ;
            swap(a+i, a+i2);
            reverse(a, i1, r);
            return true;
        }
        if (i == l) {
            reverse(a, l, r);
            return false;
        }
    }
}

void permute(char *a, int l, int r) 
{
    do {
        printf("%s\n", a);
    } while(next_permutation(a, l, r+1));
}

Demo

answered May 16, 2020 at 16:01

Nelfeal

13.3k1 gold badge23 silver badges42 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

How can a recursive call in a for loop be optimized?

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related