How to return values from recursive function to array

Question

function nestedLoop(depth::Integer, n::Integer, symbArr, len::Integer, k::Integer, num_arr)
  for i = k:len
    num_arr[depth-n+1] = symbArr[i]
    n == 1 && println(num_arr)
    (n > 1) && nestedLoop(depth, n-1, symbArr, len, i, num_arr)
  end
end

function combwithrep(symbArr, n::Integer)
  len = length(symbArr)
  num_arr = Array(eltype(symbArr),n)
  nestedLoop(n, n, symbArr, len, 1, num_arr)
end
@time combwithrep(["+","-","*","/"], 3)

I have some troubles with returning values from elementary recursive function, that computes combinations with repetitions. I can't realize how to commit replacement of println with some return to array in combwithrep() function. I have failed to use tasks for this also. The best result is to obtain iterator over this values, but it is not possible in recursion, isn't it?

I feel that the answer is simple, and i don't understand something about recursion.

Would including and returning an accumulator in your tail recursion give you want you want? — rickhg12hs
Following the Combinations iterator model to create your own Type, length, start, next, and done for an iterator would be a good exercise. — rickhg12hs
@rickhg12hs Accumulator is a kind of counter, if we are speaking about one and the same. Actually, I need combinations themselves, not a counter. But it seems I understood u not correctly about this. Could u show a few lines of code for example? — korantir
@rickhg12hs Speaking about combinations from combinatorics.jl, yes, you are right about good exercise. I knew about this iterator implemetation. But it is done without recursion. I can't understand how to implement it in recursion case. Algorithm rewriting is surely possible, but i'm trying to clarify situation with recusive functions. First of all, I want answer for simple question: is it possible to do iterator from recursive function? Thanks for help. — korantir
I've posted a way to return all the combinations. An iterator is possible, but that should probably be a separate question. — rickhg12hs

rickhg12hs rickhg12hs · Accepted Answer · 2015-05-20T09:50:39

This is certainly not optimal, but it's functional.

julia> function nested_loop{T <: Integer, V <: AbstractVector}(depth::T, n::T, symb_arr::V, len::T, k::T, num_arr::V, result::Array{V,1})
           for i = k:len
               num_arr[depth-n+1] = symb_arr[i]
               n == 1 ? push!(result, deepcopy(num_arr)) : nested_loop(depth, n-1, symb_arr, len, i, num_arr, result)
           end
       end
nested_loop (generic function with 1 method)

julia> function combwithrep(symb_arr::AbstractVector, n::Integer)
           len = length(symb_arr)
           num_arr = Array(eltype(symb_arr),n)
           result = Array{typeof(num_arr)}(0)
           nested_loop(n, n, symb_arr, len, 1, num_arr, result)
           return result
       end
combwithrep (generic function with 1 method)

julia> combwithrep(['+', '-', '*', '/'], 3)
20-element Array{Array{Char,1},1}:
 ['+','+','+']
 ['+','+','-']
 ['+','+','*']
 ['+','+','/']
 ['+','-','-']
 ['+','-','*']
 ['+','-','/']
 ['+','*','*']
 ['+','*','/']
 ['+','/','/']
 ['-','-','-']
 ['-','-','*']
 ['-','-','/']
 ['-','*','*']
 ['-','*','/']
 ['-','/','/']
 ['*','*','*']
 ['*','*','/']
 ['*','/','/']
 ['/','/','/']

How to return values from recursive function to array

1 Answers