Rekurzija

Redmond

Redmond

Elita
Poruka
17.258
Koliko često morate da pišete kodove sa funkcijama koje pozivaju same sebe? Razumete li rekurziju i da li je koristite? Meni je zasad to možda najkonfuzniji koncept u programiranju. Koliko daleko može da dogura programer koji je u potpunosti ne razume i izbegava njeno korišćenje?
 
Probaj neki funkcionalni jezik :P
Recimo, u Hascell-u nemas petlje, nego se to izvodi rekurzijom....
edit: recimo stabla su prirodno rekurzivne srukture. Kada hoce da reklamiraju
prednost funkcionalnih jezika onda pokazuju implementacije stabala.
Potom rekurzivni algoritmi za sortiranje.
evo ti merge sort u Haskellu:
Kod: 
msort xs
  | n < 2 = xs
  | otherwise = merge (msort x1s) (msort x2s)
  where
    n = length xs
    (x1s,x2s) = splitAt (n`quot`2) xs
    merge xs ys = case (xs,ys) of
      ([], ys') -> ys'
      (xs', []) -> xs'
      (x:xs',y:ys') | x < y -> x : merge xs' ys
                    | otherwise -> y : merge xs ys'
 
ovaj zadatak vezan za permutacije na codewars sajtu mi je zadavao noćne more...

In this kata you have to create all permutations of an input string and remove duplicates, if present. This means, you have to shuffle all letters from the input in all possible orders.

Examples:

permutations('a'); // ['a']
permutations('ab'); // ['ab', 'ba']
permutations('aabb'); // ['aabb', 'abab', 'abba', 'baab', 'baba', 'bbaa']
 
Redmond:
ovaj zadatak vezan za permutacije na codewars sajtu mi je zadavao noćne more...

In this kata you have to create all permutations of an input string and remove duplicates, if present. This means, you have to shuffle all letters from the input in all possible orders.

Examples:

permutations('a'); // ['a']
permutations('ab'); // ['ab', 'ba']
permutations('aabb'); // ['aabb', 'abab', 'abba', 'baab', 'baba', 'bbaa']
Kliknite za proširenje...
Mislim da je vec neko na forumu postavljao pitanje, posto vec imam non rekurzivno resenje:
Kod: 
fn main()->Result<(),String> {
    // povucemo args pa ih pretvorimo iz iteratora u vec stringova
    let mut args:Vec<String> = std::env::args().collect();
    // mora zato sto rust ne dozvojava dve reference a da je jedna mutabilna
    let len = args[1].len();
    unsafe {
        // ditto
        let mut buf = args[1].as_bytes_mut();
        // gimnastika da se bytes prikaze kao String
        println!("{:?}",buf.iter().map(|c| *c as char).collect::<String>());

        while (next_permutation(buf,len)){
            println!("{:?}",buf.iter().map(|c| *c as char).collect::<String>());
        }
    }
    Ok(())
}

fn next_permutation(s:&mut [u8], n:usize)->bool {
    let mut i = n-1;
    // dva susedna
    while(s[i-1] >= s[i]) {
        i -= 1;
        if (i == 0) {
            return false;
        }
    }
    let mut j = n-1;
    // trazi
    while (j>i && s[j]<=s[i-1] ) {
        j -= 1;
    }
    // zameni ta dva
    s.swap(i-1,j);
    // obrni od tog pa do kraja
    s[i..].reverse();
    true
}

i
Kod: 
bmaxa@Branimirs-Air rust % ./permutations aabb
"aabb"
"abab"
"abba"
"baab"
"baba"
"bbaa"
 
Evo cistije u Swiftu
Swift: 
@main
struct Main{
  static func main(){
    if CommandLine.argc>1 {
      var buf = Array(CommandLine.arguments[1])
      print(buf)
      while next_permutation(&buf) == true {
        print(buf)
      }
    }
  }
  static func next_permutation(_ s:inout [Character])->Bool{
    var i = s.count - 1
    while s[i-1] >= s[i] {
      i -= 1
      if i == 0 { return false }
    }
    var j = s.count - 1
    while ( j > i && s[j] <= s[i-1] ) {
      j -= 1
    }
    s.swapAt(i-1,j)
    s[i...].reverse()
    return true
  }
}

i
Kod: 
bmaxa@Branimirs-Air rust % ./permutations aabb
["a", "a", "b", "b"]
["a", "b", "a", "b"]
["a", "b", "b", "a"]
["b", "a", "a", "b"]
["b", "a", "b", "a"]
["b", "b", "a", "a"]
 
Redmond:
ovaj zadatak vezan za permutacije na codewars sajtu mi je zadavao noćne more...

In this kata you have to create all permutations of an input string and remove duplicates, if present. This means, you have to shuffle all letters from the input in all possible orders.

Examples:

permutations('a'); // ['a']
permutations('ab'); // ['ab', 'ba']
permutations('aabb'); // ['aabb', 'abab', 'abba', 'baab', 'baba', 'bbaa']
Kliknite za proširenje...

generisati sve permutacije i nije baš trivijalno. ja sam tu nabola leksikografski algoritam ako se tako zove, ali to nije baš efikasno za veće brojeve
https://www.baeldung.com/cs/array-generate-all-permutations
- ima tu 2-3 algoritma, heap i još nešto, al ne moraš sam da izmišljaš

e sad da izmnožiš faktorijel to je već OK vežba za rekurziju, da malo i shvatiš
n!, npr 5! = 5*4*3*2*1 - ok je primer.
verovatno možeš da ne koristiš to nikada ali eto prođi malo pa ti možda nekad dođe iz mozga. obično na ovim vežbaonica-sajtovima ima nešto na tu temu, možda na intervjuima za posao, a konkretno verovatno ne ideš u neke dubine osim ako je takvo radno mesto
 
Prijavite se ili registrujte da biste poslali poruku.

Back
Top