-1

I am trying to generate a combination of numbers in python list using recursion and my code is as follows

nums = [2,3,4,6]

def backtrck(temp, starting_index, nums):
    if len(temp) == 2:
        print(temp)
        return
    temp.append(nums[starting_index])
    for i in range(starting_index + 1, len(nums)):
        backtrck(temp, i, nums)

backtrck([], 0, nums)

for some reason, the above code is unable to generate the proper combinations.

Aim of the code: I want to generate all the combination of numbers starting with index 0 whose length should be equal to 2

expected output

[2, 3]
[2, 4]
[2, 6]

actual output

[2, 3]
[2, 3]
[2, 3]
[2, 3]

I don't understand what is going wrong with this recursion, I am hoping that someone could help me figure this out

USK
  • 23
  • 4
  • You should be checking several things in your code.Like the `return`, you are not returning anything. Also as the tell you in the answer, if you need a single iteration, not sure what is the point of using recursion – Ignacio Alorre Jan 17 '21 at 15:06
  • 1
    You should use a debugger or [this site](http://pythontutor.com) to step through your code and observe what it is doing. – mkrieger1 Jan 17 '21 at 15:09
  • @IgnacioAlorre `return` doesn't need to return anything for it to be used properly. The `return` statement in the function is to stop continuing to parse the loop. – Red Jan 17 '21 at 15:20
  • If you are using an IDE **now** is a good time to learn its debugging features Or the built-in [Python debugger](https://docs.python.org/3/library/pdb.html). Printing *stuff* at strategic points in your program can help you trace what is or isn't happening. [What is a debugger and how can it help me diagnose problems?](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems) – wwii Jan 17 '21 at 16:48

3 Answers3

3

Recursion is unnecessary when you can simply use for loop:

nums = [2,3,4,6]

def backtrck(starting_index, nums):
    start = nums[starting_index]
    for num in nums[starting_index + 1:]:
        print([start, num])
        
backtrck(0, nums)

Output:

[2, 3]
[2, 4]
[2, 6]

where the slice nums[start_index + 1:] returns a list of all the elements of the nums list starting from one indice after the starting_index.

UPDATE

Since you've pointed out that the recursion was necessary in your code, simply replace the backtrck(temp, i, nums) recursive call with backtrck(i, nums, [temp[0], nums[i]]) to keep the starting index of the list:

nums = [2, 3, 4, 6]

def backtrck(starting_index, nums, temp=[]):
    if len(temp) == 2:
        print(temp)
        return
    temp.append(nums[starting_index])
    for i in range(starting_index + 1, len(nums)):
        backtrck(i, nums, [temp[0], nums[i]])

backtrck(0, nums)

Output:

[2, 3]
[2, 4]
[2, 6]

Note that I've changed the positional argument temp into a keyword argument. It will still work with temp as a positional argument, but it will be less practical if the temp list always starts out as empty.

Red
  • 26,798
  • 7
  • 36
  • 58
  • Thanks for the alternative approach. But the question I asked is a part of a bigger problem that is specifically asked to be solved in recursion. That is the reason I have asked for the recursive approach – USK Jan 17 '21 at 15:03
  • 1
    You certainly *made it recursive* but it's kinda *tricky*. :) – wwii Jan 17 '21 at 16:18
2

What is wrong with your function:

After couple of recursive calls temp becomes [2,3] then on the next recursion your base case is met (len(temp) == 2:) and that instance of the function returns without adding anything. The next for loop iteration recurses and the same thing happens. Once temp is [2,3] it can never change.

How to fix it:

There are a number of problems with the structure of your function and it is not a simple one-line-fix. You need to figure out how to

  • when the base case is met
    • capture (or print) temp
    • return something meaningful to the previous function that it can use to continue making combinations
  • the function needs to act upon the return value from the recursive call
  • adding a for loop to a recursive procedure/process complicates things, maybe figure out how to do without it.

I would start over with the function. I don't know if you are asking someone to give you a completely new function so I'm going to search for questions regarding recursive solutions to find/generate list item combinations.

Here are some related SO Questions/Answers. If any of them solve your problem let us know so we can mark yours as a duplicate. Most don't have the taken two-at-a-time constraint but maybe you can adapt. there are many more.

Recursive function that returns combinations of size n chosen from list
Recursively find all combinations of list
python recursion list combinations without using generator
Using recursion to create a list combination

Loosely related:
Nth Combination
Finding all possible combinations of numbers to reach a given sum
Creating all possible k combinations of n items in C++ - not Python but algorithms might be useful.

wwii
  • 23,232
  • 7
  • 37
  • 77
1

When it comes to recursion, my advice is keep it simple and let the recursion do the work for you:

def backtrck(numbers):
    if len(numbers) < 2:
        return []

    first, second, *rest = numbers

    return [[first, second]] + backtrck([first] + rest)

nums = [2, 3, 4, 6]

print(*backtrck(nums), sep='\n')

OUTPUT

> python3 test.py
[2, 3]
[2, 4]
[2, 6]
>
cdlane
  • 40,441
  • 5
  • 32
  • 81