Find integers between 1 and the biggest N-bits using recursion in python

Question

I need to find the integers between 1 and the biggest N-bits integer,eg: when n = 3. I need to return 1...999. And using recursion. The following is my code.The problem is that I don't know the exact data structure to represent the number. Accurate to return (n=2): [1,2,3,....99], but I return [[0,0],[0,1],..[9,9]].I use list to represent the number. Does anyone know the exact forn to represent the numbers?

class Solution:
# @param n: An integer.
# return : A list of integer storing 1 to the largest number with n digits.
def setOnebyOne(self,numList,number,n,index):
    if index == n-1:
        print 'index = n-1',n-1,number
        numList.append(number)
        return numList

    print index,'setting',number

    for i in range(10):
        if i == 0:
            number.append(i)
        else:
            number[index+1] = i
        print number
        self.setOnebyOne(numList, number,n,index+1)  

def numbersByRecursion(self, n):
    # write your code here
    if n <1:
        return None
    numList = []
    for i in range(10):
        print i
        number =[]
        print number
        number.append(i)
        print 'number[0]= ',number
        self.setOnebyOne(numList, number,n,0)

This sounds very much like an homework assignment. Besides your example with n=3 should not be 1...999 but 1...7 (if it is unsigned). Maybe a hint: DON'T use for loops in recursive functions. — hr0m, Mar 27 '16 at 14:09
Oh I seemed to do not explain it clearly. It is talked in decimal not in binary. So it is 1...999 if n=3 — liuxy, Mar 28 '16 at 02:20

score 1 · Answer 1 · edited May 23 '17 at 12:31

1

This is one way to do it.

class Solution():
    def __init__(self,inp):
        self.inp = inp
        self.val = pow(10,inp) - 1
        self.ans = []

    def solution(self):
        if self.val>0:
            self.ans.append(self.val)
            self.val-=1
            self.solution()


inp = input()
sol = Solution(inp)

sol.solution()
print sol.ans

Also you might wanna see this. Recursion in Python? RuntimeError: maximum recursion depth exceeded while calling a Python object

Python has a recursion depth limit .

Check it out by executing

import sys
print sys.getrecursionlimit()

EDITED

def numbersByRecursion(n,largest,result):`
    def recursion(num,largest,result):
        if num <= largest:
            result.append(num)
            return recursion(num+1,largest,result) 
        else:
            return result
    return recursion(n,largest,result)


result = []
n = input()
largest = pow(10,n) - 1
ans = numbersByRecursion(1,largest,result)
print ans

edited May 23 '17 at 12:31

Community

1
1

answered Mar 27 '16 at 14:27

formatkaka

1,278
3
13
27

I'm upset because I got another problem.I change my code like you but I didn't get the result. The code I write is `def numbersByRecursion(self, n): result = [] recursion(i,largest,result) def recursion(num,largest,result): if num > largest: return result result.append(num) recursion(num+1,largest,result)` print the result as [1,2,3,4,5,6,7,8,9],but it return None. It seems beacause list has None type to return,but it should have return a list of integers.How can I fix this problem? – liuxy Mar 28 '16 at 03:20
Hie check out the answer. Posted the edit for your comment. – formatkaka Mar 28 '16 at 05:04
Sorry I proposed the comment so ugly :( ,I am new to stackoverflow .And I figured out that I didn't include return at the end of the function 'numberByRecursion'. As the last return in your program'return recursion(n,largest,result)' .So it return None. The return in recursion makes me confused! – liuxy Mar 28 '16 at 07:22
Yes, that was the reason it was returning None.Hope your query is resolved. – formatkaka Mar 28 '16 at 07:29

score 0 · Answer 2 · answered Mar 27 '16 at 14:15

If your question is how to beat a list like

list = [[0,0], [0,1], [0,2], ... , [9,9]]

into

result_list = [0, 1, 2, 3, ..., 99]

then you could do:

def format_list(list):
    result_list = []
    for item in list:
        result = 0
        power = len(item)*10
        for digit in item:
            result += digit ** power
            power /= 10
        result_list.append(result)
    return result_list

Disclaimer: Didn't test this

itzMEonTV · Answer 3 · 2016-03-27T14:48:07.833

0

Try this

def myfn(n):
    def myfn2(i):
        if i==int(n*'9'):
            return [int(n*'9')]
        return [i]+myfn2(i+1)
    return myfn2(1)

This gives

>>>myfn(2)
[1,2,.....,98,99]

Hope this helps

edited Mar 27 '16 at 14:48

answered Mar 27 '16 at 14:33

itzMEonTV

19,851
4
39
49

Find integers between 1 and the biggest N-bits using recursion in python

3 Answers3