how to stop a recursive function in c? [closed]

Question

void solver(char s[], FILE* PD, FILE* PI) {
    if (CONDITION)
        give(s, PD, PI);
    else 
        for (int u = 0; u < strlen(s) ;u++) {
            solver(delete_from(s, u), PD, PI);
    }
}

where:

give: is a void function, prints all strings that exist in the dictionary and have the same characters of s and same length.

delete_from: deletes the character at the uth position. (order of characters in s doesn't matter).

s: array of letters.

goal: solver function searches and display the longest word for a given string char s[] then starts by searching for the 10 letter words, if there are none it will increase to 9 letters, then 8 letters and so on using well on the letters of the draw made. this recursive function is going to build a tree.

my problem is: if for instance it printed words that contain 7 characters of s, how can it prevent the other solver functions to continue. because we don't need words composed of n-1 letters if we found words composed of n letters. thanks!

Answer 1

To solve the specific issue you asked about, you need to use a breadth first search instead of a depth-first (recursive) search.

If you delete one letter, it might find a match of length 3.

But if you delete another letter, it could find a match of length 4.

If you were to print the results in from first branch, they would be the wrong results.

Using a breadth-first search would solve this problem, and allow the search to be completed sooner.

---

But that's not the only problem.

If you delete one letter, it might find a match of length 3.

If you delete another letter, it could different matches of length 3.

You need to keep searching for results of the same length as results you've already found. And you have to watch out for duplicates!

---

Here's what I would do. I would create a trie like this one from the word list:

a
  c
    o
      t   [ "taco" ]
    t     [ "act", "cat" ]
  e
    d
      l   [ "deal", "lead" ]

Then all you can use the following:

// Returns a copy of word with the characters in ascending order.
// For example, "taco" -> "acot"
char *key(const char *word) {
   // ...
}


void solver( Trie *root_trie, const char* root_word ) {
   size_t found = 0;

   size_t root_len = strlen( root_word );
   char *root_key = key( word );

   Queue_t q;
   Queue_init( &q );

   {
      State *state = State_new( root_len, root_trie, root_key );
      Queue_enqueue( &q, state );
   }

   while ( State *state = Queue_dequeue( &q ) ) {
      size_t len  = state->len;
      Trie  *trie = state->trie;
      char  *key  = state->key;

      free( state );

      if ( len < found )
         continue;

      int last_ch = EOF;
      for ( ; *key; ++key ) {
         int ch = *key;

         if ( ch != last_ch ) {
            last_ch = ch;

            State *state = State_new( len-1, trie, key+1 );
            Queue_enqueue( &q, state );
         }

         trie = Trie_subtrie_for( trie, ch );
      }

      if ( trie ) {
         Array *matches = Trie_root_value( trie );
         if ( matches ) ) {
            size_t n = Array_len( matches );
            if ( n ) {
               found = len;

               for ( size_t i=0; i<n; ++i )
                  printf( "%s\n", Array_get( matches, i ) );
            }
         }
      }
   }

   Queue_destroy( &q );
   free( root_key )
}

The if ( ch != last_ch ) prevents duplicate searches and results.

Proof of concept:

use 5.022;
use warnings;

sub trie_lvalue :lvalue {
   my $p = \shift;
   $p = \( $$p->{$_} ) for @_;
   return $$p->{_val};
}

sub trie_rvalue {
   my $trie = shift;
   return undef if !$trie;

   for ( @_ ) {
      $trie = $trie->{$_};
      return undef if !$trie;
   }

   return $trie->{_val};
}

sub key {
   my $s = shift;
   return [ sort split //, $s ];
}

#
# Creates a trie of arrays from the dictionary file.
#
#    a
#      c
#        o
#          t   [ "taco" ]
#        t     [ "act", "cat" ]
#      e
#        d
#          l   [ "deal", "lead" ]
#
sub prep {
   my $qfn = shift;
   open( my $fh, '<', $qfn )
      or die( "Can't open \"$qfn\": $!\n" );

   my $trie = { };
   while ( my $word = <$fh> ) {
      chomp( $word );
      next if $word ne lc( $word );

      my $key = key( $word );
      push @{ trie_lvalue( $trie, @$key ) }, $word;
   }

   return $trie;
}

sub subkey {
   my $key = shift;
   my $i   = shift;
   return [ $key->@[ $i .. $#$key ] ];
}

sub solver {
   my $root_trie = shift;
   my $root_word = shift;

   my $found = 0;
   my @queue = [ length( $root_word ), $root_trie, key( $root_word ) ];
   while ( @queue ) {
      my ( $len, $trie, $key ) = @{ shift( @queue ) };

      # Don't need to look further.
      last if $len < $found;

      my $last_ch = "";
      for my $i ( 0 .. $#$key ) {
         my $ch = $key->[ $i ];

         if ( $ch ne $last_ch ) {  # Avoid duplicate results and duplicate searches.
            $last_ch = $ch;

            my $subkey = subkey( $key, $i+1 );
            push @queue, [ $len-1, $trie, $subkey ];
         }

         $trie = $trie->{ $ch }
            or last;
      }

      if ( $trie ) {
         if ( my $matches = $trie->{_val} ) {
            $found = $len;
            say for @$matches;
         }
      }
   }
}

{
   @ARGV == 2
      or die( "usage\n" );

   solver( prep( $ARGV[0] ), $ARGV[1] );
}

$ time perl a.pl /usr/share/dict/words catx
tax
act
cat

real    0m1.045s
user    0m0.995s
sys     0m0.050s

$ time perl a.pl /usr/share/dict/words dfaskfhdasklfhdaskjf
halakahs
halakhas

real    0m0.997s
user    0m0.977s
sys     0m0.020s

$ time perl a.pl /usr/share/dict/words vzxvcmnzxcewcruwou
uncover
concrew

real    0m1.059s
user    0m1.019s
sys     0m0.040s

$ time perl a.pl /usr/share/dict/words vvvvvvvvvvvvvvvvvvvvvvi
v
i

real    0m1.006s
user    0m0.946s
sys     0m0.060s